Cod sursa(job #1688600)

Utilizator Mihai9Oniga Mihai Mihai9 Data 13 aprilie 2016 16:58:18
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
char s[2000000];int d[2000000],a[2000000];
int i,n,k,cap,sp,in,t,nr,ok,l,j;
int main(){
 fin>>n>>k;fin.get();
 fin.getline(s,2000000);
 l=strlen(s);
 for(i=0;i<l;i++){
  if(s[i]==' '){
   if(ok==1){a[++j]=-nr;}
   else{a[++j]=nr;}
   nr=ok=0;
  }
  else if(s[i]=='-'){ok=1;}
  else{nr=nr*10+s[i]-'0';}
 }
 if(ok==1)a[n]=-nr;
 else{a[n]=nr;}
 nr=-10000000;cap=1;sp=0;
 for(i=1;i<=n;i++){
  while(cap<=sp&&a[i]<a[d[sp]]){--sp;}
  d[++sp]=i;
  if(i-k==d[cap]){cap++;}
   if(i>=k&&nr<a[d[cap]]){
    nr=a[d[cap]];
    in=i-k+1;
    t=i;
   }
 }
 fout<<in<<" "<<t<<" "<<nr;
 return 0;
}