Cod sursa(job #1184235)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 11 mai 2014 19:52:02
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream>
#include<string.h>
#define nmax 500009
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int sol = -40000,v[nmax],deq[nmax],k,front,back,n,x2;
char s[10*nmax];
int main()
{
    in>>n>>k;
    in.get();
    in.get(s,10*nmax);
    int i,j=0,semn = 0,len = strlen(s);
    ++len;
    s[len-1] = ' ';
    front = 1;
    back = 0;
    int nr = 0,d = 0;
    for(i = 0 ; i < len ; i++)
    {
        if(s[i]<='9' && s[i] >='0') nr= nr*10+s[i]-'0';
        if(s[i] == '-') semn = 1;
        if(s[i] == ' '){
            v[++d] = nr;
            if(semn == 1)
                v[d] = -v[d];
            semn = nr = 0;
        }
    }
    for(i = 1 ; i <= n ; i++)
    {
        while(front <= back && v[i] <= v[deq[back]])
            --back;
        deq[++back] = i;
        if(deq[front] == i-k) front++;
            if(v[deq[front]] > sol && i >= k){
                sol = v[deq[front]];
                 x2 = i;
                 }

    }

    out<<x2-k+1<<" "<<x2<<" "<<sol;
    return 0;
}