Cod sursa(job #188235)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 7 mai 2008 11:59:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define INF 2000000000
#define MAX_N 500010
using namespace std;
int v[MAX_N],n,k;
struct el {
        int vl,deadline;
} deq[MAX_N];
char s[7000000];

void iofile(void){

        freopen(FIN,"rt",stdin);
        freopen(FOUT,"wt",stdout);
        scanf("%d %d\n",&n,&k);

        fgets(s+1,7000000,stdin);

        int len=strlen(s+1)-1;
        int i=1;
        int ind=0,p=1,x=0;
        while (i<=len){
            p=1;
            x=0;
            if (s[i]=='-'){p=-1;++i;}
            for (;s[i]!=' ' && i<=len;++i){
                    x*=10;x+=s[i]-'0';
            }
            ++ind;
            v[ind]=x*p;
            ++i;
        }
        

        fclose(stdin);
}


void solve(void){
    int pin,maxim=-INF,time=1;
    int st=1,dr=1;
    deq[1].vl=v[1];
    deq[1].deadline=1+k;
    for (int i=2;i<=n;++i){
        ++time;
        while (st<=dr && deq[st].deadline<=time){++st;}
        while (dr>=st && deq[dr].vl>v[i]){--dr;}
        ++dr;
        deq[dr].vl=v[i];
        deq[dr].deadline=i+k;
        if (i>=k && deq[st].vl>maxim){maxim=deq[st].vl;pin=deq[dr].deadline-k-k+1;}
    }
    int pend=pin+k-1;
    while (pin>1 && v[pin-1]>=maxim){--pin;}
    printf("%d %d %d\n",pin,pend,maxim);

    fclose(stdout);
    return;
}

int main(void){
    iofile();
    solve();
    return 0;
}