Cod sursa(job #2206715)

Utilizator Raresr14Rosca Rares Raresr14 Data 23 mai 2018 15:48:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n,i,p,u,v[500010],D[500010],k,maxim,poz1,poz2,semn,val,h;
char c[20000010];
int main(){
    fin>>n>>k;
    fin.get();
    fin.get(c,20000000);
    maxim=-2000000000;
    semn=1;
    for(i=0;c[i]!=0;i++){
        if(c[i]=='-'){
            semn=-1;
            continue;
        }
        if(c[i]=='+'){
            semn=1;
            continue;
        }
        if(c[i]>='0'&&c[i]<='9'){
            val=val*10+c[i]-'0';
            continue;
        }
        if(c[i]==' '&&(c[i-1]>='0'&&c[i-1]<='9')){
            v[++h]=val*semn;
            semn=1;
            val=0;
        }
    }
    v[++h]=val*semn;
    p=1;
    u=1;
    D[1]=1;
    for(i=2;i<=h;i++){
        while(p<=u&&v[i]<v[D[u]])
            u--;
        D[++u]=i;
        if(i-D[p]==k)
            p++;
        if(i>=k&&v[D[p]]>maxim){
            maxim=v[D[p]];
            poz1=D[u]-k+1;
            poz2=D[u];
        }
    }
   fout<<poz1<<" "<<poz2<<" "<<maxim;
}