Cod sursa(job #972571)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 12 iulie 2013 10:20:46
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int Deque[500003],N,K,Arr[500003],Begin,End,ind;
string Number;
long long sum;
int power(int x,int y)
{
    int i,p=1;
    for(i=1;i<=y;i++)
        p*=x;
    return(p);
}
int AtribValue()
{
    int i,sign=1,start=1;
    int result=0;
    ind++;
    if(Number[ind]=='-')
    {
        sign=-1;
        ind++;
    }
    while(Number[ind]!=' ')
    {
        result=result*10+Number[ind]-'0';
        ind++;
    }
    return result*sign;
}
void Read_and_Process()
{
    f>>N>>K;
    int i,maximum=-32001,end;
    Begin=1;
    End=0;
    f.get();
        getline(f,Number);
        Number+=' ';
    for(i=1;i<=N;i++)
    {
        Arr[i]=AtribValue();
        if(i<K)
        {
            while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
                End--;
            Deque[++End]=i;
            continue;
        }
        if(i==K)
        {
            while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
                End--;
            Deque[++End]=i;
            if(Arr[Deque[Begin]]>maximum)
            {
                maximum=Arr[Deque[Begin]];
                end=K;
            }
            continue;
        }
        if(i>K)
        {
            while(Begin<=End&&Arr[i]<=Arr[Deque[End]])
                End--;
            Deque[++End]=i;
            if(Deque[Begin]==i-K)
                Begin++;
            if(Arr[Deque[Begin]]>maximum)
            {
                maximum=Arr[Deque[Begin]];
                end=i;
            }
        }
    }
    g<<end-K+1<<" "<<end<<" "<<maximum<<"\n";
}
int main()
{
    Read_and_Process();
    return 0;
}