Cod sursa(job #982507)

Utilizator classiusCobuz Andrei classius Data 9 august 2013 12:51:21
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <deque>
#include <string>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

int main()
{
    int n,k,mi=0,mj=0,mx=-1000000;
    short v[500001]={};

    f>>n>>k; f.ignore();
    char *a=new char[n*7];
    f.read(a,n*7);

    unsigned j=0;
    for(int i=1;i<=n;i++){
        int sgn=1;
        if(a[j]=='-') { sgn=-1; j++;}
        while(isdigit(a[j])){
            v[i]=v[i]*10+a[j]-'0';
            j++;
        }
        j++;
        v[i]*=sgn;
    }

    deque<int> dq;

    for(int i=1;i<=n;i++){

        while(!dq.empty()&&dq.front()<=i-k)
            dq.pop_front();

        while(!dq.empty()&&v[i]<v[dq.back()])
            dq.pop_back();

        dq.push_back(i);

        if(i>=k&&v[dq.front()]>mx)
            mx=v[dq.front()],mi=i-k+1,mj=i;
    }

    g<<mi<<" "<<mj<<" "<<mx;

    return 0;
}