Cod sursa(job #188193)

Utilizator vanila_CPPIonescu Victor Cristian vanila_CPP Data 7 mai 2008 01:32:02
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 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,MAX_N,stdin);

        int def=0;

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

        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;
}