Cod sursa(job #292270)

Utilizator katamashCatalin Tamas katamash Data 30 martie 2009 22:11:35
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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;}