Cod sursa(job #931329)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 28 martie 2013 10:15:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<cstdio>
#include<deque>
#include<cstring>
#define nmax 500010
using namespace std;
deque<int>q;
int n,k,i,x[nmax],crt,sol=-30010,poz,ok;
char sir[4000000];
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d\n", &n, &k);
    fgets(sir,4000000,stdin);
    for(i=1;i<=n;++i)
    {
        if(sir[poz]=='-'){ok=-1;++poz;}
        else ok=1;
        for(;0<=sir[poz]-'0'&&9>=sir[poz]-'0';++poz)x[i]=x[i]*10+(sir[poz]-'0');
        x[i]*=ok;
        ++poz;
    }
    for(i=1;i<=n;++i)
    {
        while(q.size()&&x[q.back()]>=x[i])
            q.pop_back();
        q.push_back(i);
        if(q.front()==i-k)
            q.pop_front();
        if(i>=k&&x[q.front()]>sol)
        {
            sol=x[q.front()];
            crt=i;
        }
    }
    printf("%d %d %d\n", crt-k+1, crt, sol);
    return 0;
}