Cod sursa(job #2205777)

Utilizator anamariatoaderAna Toader anamariatoader Data 20 mai 2018 11:33:31
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n,k,i,j,p,u,v[500001],q[500001],Max,dr,nr,ok;
char s[3500002];
int main()
{
    fin>>n>>k;
    fin.get();//elimin enterul
    fin.getline(s+1,3500002);nr=0;j=0;
    for(i=1;s[i]!='\0';i++)
        if(s[i]!=' '){
           if(s[i]=='-')
              ok=1;
           else
            nr=nr*10+s[i]-'0';
        }
        else{
           if(ok==1)
             nr=-nr;
            v[++j]=nr;
            nr=0;ok=0;
        }
  if(ok==1)
            nr=-nr;
    v[++j]=nr;
        n=j;
    Max=-30001;
    p=1;
    u=0;
    for(i=1;i<=n;i++){

        while(p<=u&&v[i]<v[q[u]]){
            u--;
        }
        q[++u]=i;
        while(p<=u&&q[u]-q[p]>=k)
            p++;
        if(i>=k&&v[q[p]]>Max){
            Max=v[q[p]];
            dr=i;
        }
    }
    fout<<dr-k+1<<" "<<dr<<" "<<Max;
    return 0;
}