Cod sursa(job #1526760)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 17 noiembrie 2015 10:24:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<cstdio>
#define dim 8192
using namespace std;
int v[500010],poz=0;
char buff[dim];
struct jmenuiala{int val,poz;};
jmenuiala q[500010];
void citeste(int &numar){
    int sg=1;
    numar=0;
    while((buff[poz]<'0'||buff[poz]>'9')&&buff[poz]!='-'){
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    if(buff[poz]=='-'){
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
        sg=-1;
    }
    while(buff[poz]>='0'&&buff[poz]<='9'){
        numar=numar*10+buff[poz]-'0';
        poz++;
        if(poz==dim){
            fread(buff,1,dim,stdin);
            poz=0;
        }
    }
    numar*=sg;
}
int main(){
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,left=1,right=0,ans,i,l,r,x;
    fread(buff,1,dim,stdin);
    citeste(n);
    citeste(k);
    for(i=1;i<=n;i++){
        citeste(x);
        v[i]=x;
    }
    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;
}