Cod sursa(job #297286)

Utilizator QSilverGeorge Popa QSilver Data 5 aprilie 2009 12:04:05
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 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;}