Cod sursa(job #290790)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 28 martie 2009 19:01:56
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<algorithm>
using namespace std;

#define DIM 50001
#define INF -1000001

int n,k,a[DIM],q[DIM];

void solve(){
    int i,st,dr,poz,sol;

    scanf("%d%d",&n,&k);
    for(i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    for(i=st=1,dr=0; i<k; ++i){
        for(; dr>=st&&a[i]<=a[q[dr]]; --dr);
        q[++dr]=i;}
    for(i=k,sol=INF; i<=n; ++i){
        for(; st<=dr&&a[i]<=a[q[dr]]; --dr);
        q[++dr]=i;
        for(; st<=dr&&q[st]<i-k+1; ++st);
        if(a[q[st]]>sol){
            sol=a[q[st]];
            poz=i;}}
    printf("%d %d %d",poz-k+1,poz,sol);}

int main(){

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    solve();
    return 0;}