Cod sursa(job #1173119)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 18 aprilie 2014 17:30:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<cstdio>
#include<deque>
using namespace std;
const int MAX=30000,N=500000,NRD=6;
deque<int>d;
int v[N+1];
char s[N*NRD+N+1];
int n,maximum=-MAX-1,l,r,b,k;
void scan(){
    int i=0,j=0,nr=0;
    bool f=false;
    scanf("%d%d\n",&n,&k);
    gets(s);
    while(s[i]!='\0'){
        if(s[i]=='-')
            f=true;
        else if(s[i]==' '){
            v[++j]=nr;
            if(f)
                v[j]*=-1;
            nr=0;
            f=false;
        }
        else
            nr=nr*10+s[i]-'0';
        i++;
    }
    v[n]=nr;
    if(f)
        v[i]*=-1;
}
void init(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scan();
    scanf("%d%d",&n,&k);
}
void solve(){
    int i;
    for(i=1;i<=n;i++){
        while(!d.empty()&&v[i]<=v[d.back()])
            d.pop_back();
        d.push_back(i);
        if(d.front()==i-k)
            d.pop_front();
        if(v[d.front()]>maximum&&i>=k){
            maximum=v[d.front()];
            l=i-k+1;
            r=i;
        }
    }
}
int main(){
    init();
    solve();
    printf("%d %d %d",l,r,maximum);
    return 0;
}