Cod sursa(job #1526749)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 17 noiembrie 2015 10:09:44
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
using namespace std;
int v[500010];
struct jmenuiala{int val,poz;};
jmenuiala q[500010];
int main(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,left=1,right=0,ans,i,l,r;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(i=1;i<=k;i++){
        while(right>left&&v[i]<=q[right].val)
            right--;
        right++;
        q[right].poz=i;
        q[right].val=v[i];
    }
    ans=q[1].val;
    l=1;
    r=k;
    for(i=k+1;i<=n;i++){
        while(right>left&&v[i]<=q[right].val){
            q[right].val=q[right].poz=0;
            right--;
        }
        right++;
        q[right].poz=i;
        q[right].val=v[i];
        while(q[left].poz<=i-k)
            left++;
        if(q[left].val>ans){
            ans=q[left].val;
            l=i-k+1;
            r=i;
        }
    }
    printf("%d %d %d",l,r,ans);
    return 0;
}