Cod sursa(job #972559)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 12 iulie 2013 08:59:51
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int Deque[500003],N,K,Arr[500003],Begin,End;
int Secv[500003];
long long sum;
void read()
{
    f>>N>>K;
    int i;
    for(i=1;i<=N;i++)
        f>>Arr[i];
}
void calculate()
{
    int i,maximum=-32001,end;
    Begin=1;End=0;
    for(i=1;i<=K;i++)
    {
        while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
            End--;
        Deque[++End]=i;
    }
    Secv[K]=Arr[Deque[Begin]];
    if(Secv[K]>maximum)
    {
        maximum=Secv[K];
        end=K;
    }
    for(i=K+1;i<=N;i++)
    {
        while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
            End--;
        Deque[++End]=i;
        if(Deque[Begin]==i-K)
            Begin++;
        Secv[i]=Arr[Deque[Begin]];
        if(Secv[i]>maximum)
        {
            maximum=Secv[i];
            end=i;
        }
    }
    g<<end-K+1<<" "<<end<<" "<<maximum<<"\n";
}
/*void print()
{
    int i,maximum=-32001,end;
    for(i=K;i<=N;i++)
    {
        if(Secv[i]>maximum)
        {
            maximum=Secv[i];
            end=i;
        }
    }
    g<<end-K+1<<" "<<end<<" "<<maximum<<"\n";
}*/
int main()
{
    read();
    calculate();
    return 0;
}