Cod sursa(job #972616)

Utilizator nparfene2004Parfene Narcis nparfene2004 Data 12 iulie 2013 11:32:14
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#define Dim 500001
 
using namespace std;

int q[Dim] ;
long ind[Dim] ;
 
int main()
{
 int x, maxim ;
 long poz, pr, ul, n, k, i, p ;
 
 ifstream fin("secventa.in");
 ofstream fout("secventa.out");
 
 fin >> n >> k;
 
 // calculez minimul din primele k:
 pr = 0 ; ul = -1 ;
 for (i=1; i<=k; i++)
  {
   fin >> x;
   while ((pr<=ul)&&(q[ul] >= x)) ul-- ;
   q[++ul] = x ;
   ind[ul] = i ;
  }
 maxim = q[pr] ;
 poz = 1 ;
 p = 1;
 // calculez restul:
 for ( ; i<=n; i++)
  {
   fin >> x;
   while ((q[ul] >= x) && (pr<=ul)) ul-- ;
   q[++ul] = x ;
   ind[ul] = i ;
   p++ ;
   if (ind[pr] <= i-k) pr++ ;
   if (maxim < q[pr]) { maxim = q[pr] ;poz = p; }
  }
 
 fout << poz << " " << (poz + k -1) << " " << maxim << "\n";

 fin.close();
 fout.close();
 
 return 0 ;
}