Cod sursa(job #1430022)

Utilizator lraduRadu Lucut lradu Data 7 mai 2015 19:14:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <iostream>
#include <string>
#include <stdio.h>
#include <fstream>


using namespace std;
int n,k;
int first,mxm=-30001,last,le,ri;
int v[500001],deque[500001];
string line;

int main()
{

 ifstream f("secventa.in");
 ofstream g("secventa.out");

 f>>n>>k;
 getline(f,line);
 getline(f,line);
 int m=1,nr=0;
 bool ok=false;
 for (int i=0; i<line.size(); i++)
 {
     if(line[i]!='-')
     {
         if(line[i]!=' ')
            nr=nr*10+(line[i]-'0');
         else
         {
             if(ok==true)
             {
                v[m]=nr*(-1);
                ok=false;
             }
             else
                v[m]=nr;
             m++;
             nr=0;
         }
         if(i+1==line.size())
         {
           if(ok==true)
                v[m]=nr*(-1);
           else
                v[m]=nr;
         }
     }
     else
        ok=true;
 }

 le=1;
 ri=0;
 for(int i=1;i<=n;i++)
 {
  while(le<=ri && v[i]<=v[deque[ri]])
   --ri;

  deque[++ri]=i;

  if(deque[le]==i-k)
   ++le;

  if(i>=k)
   if(v[deque[le]]>mxm)
   {
    mxm=v[deque[le]];
    first=i-k+1;
    last=i;
   }
 }

 g<<first<<" "<<last<<" "<<mxm;

 return 0;
}