Cod sursa(job #292376)

Utilizator lexu93Todor Alex lexu93 Data 31 martie 2009 08:41:52
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<algorithm>      
using namespace std;      
     
#define DIM 500001      
#define INF -1000001      
     
int n,k,q[DIM];      
short a[DIM];      
     
void read(){      
    int i,m,lg,nr,semn;      
    char s[7*DIM];      
     
    scanf("%d%d\n",&n,&k);      
    gets(s);      
    lg=strlen(s);      
    for(i=m=0,semn=1; i<lg; ++i)      
        if(s[i]=='-')      
            semn=-1;      
        else if(isdigit(s[i])){      
            for(nr=0; isdigit(s[i]); nr=nr*10+s[i]-'0',++i);      
            a[++m]=nr*semn;      
            semn=1;}}      
     
void solve(){      
    int i,st,dr,poz,sol;      
     
    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);      
    read();      
    solve();      
    return 0;}