Cod sursa(job #1173106)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 18 aprilie 2014 17:15:46
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<cstdio>
#include<deque>
using namespace std;
const int MAX=30000,N=500000;
deque<int>d;
int v[N+1];
int n,maximum=-MAX-1,l,r,b,k;
void init(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
}
void solve(){
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&v[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;
}