Cod sursa(job #997976)

Utilizator Corneliu10Dumitru Corneliu Corneliu10 Data 15 septembrie 2013 13:03:50
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
  
using namespace std;
  
char sir[4000050];
int q[500010],ind[500010];
  
inline int Creeaza(int &indice)
{
    int sign,x;
    if(sir[indice]=='-')
    {
        sign=-1;
        indice++;
    }
    else
        sign=1;
    x=0;
    while(sir[indice]>='0' && sir[indice]<='9')
    {
        x=x*10+sir[indice]-'0';
        indice++;
    }
    indice++;
    return x*sign;
}
  
int main()
{
    int n,k,i,pr,ul,x,max,poz,p,indice;
    ifstream fin("secventa.in");
    ofstream fout("secventa.out");
    fin>>n>>k;
    fin.get();
    fin.getline(sir,3500000);
    pr=0;ul=-1;indice=0;
    for (i=1;i<=k;i++)
    {
       x=Creeaza(indice);
       while ((pr<=ul)&&(q[ul] >= x)) ul-- ;
       q[++ul] = x ;
       ind[ul] = i ;
    }
    max = q[pr] ;
    poz = 1 ;
    p = 1;
    for ( ; i<=n; i++)
    {
       x=Creeaza(indice);
       while ((q[ul] >= x) && (pr<=ul)) ul-- ;
       q[++ul] = x ;
       ind[ul] = i ;
       p++ ;
       if (ind[pr] <= i-k) pr++ ;
       if (max < q[pr]) { max = q[pr] ;poz = p; }
    }
    fout<<poz<<" "<<poz+k-1<<" "<<max;
    fin.close();
    fout.close();
    return 0;
}