Cod sursa(job #47586)

Utilizator RazvanSSavu Razvan RazvanS Data 3 aprilie 2007 20:19:04
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#define Nmax 500001


using namespace std;
int V[Nmax], Q[Nmax];

int main(void)
    {//int a=1;
     //if(a) return 0;
     int n, k;
     freopen("secventa.in", "r", stdin);
     scanf("%d %d", &n , &k);
     int i;
     for(i=1;i<=n;++i)
        scanf("%d ", &V[i]);
      
     //ofstream fout("test123.out");fout<<"fasfds"; fout.close();   
     
     int max=0, p=0;
     int end=0, beg=1;
     
     freopen("secventa.out", "w", stdout);
     
     for(i=1;i<=n;++i)
          {
           while(beg <= end && Q[beg]<= i-k) beg++;
           
           while(beg<=end &&  V[ Q[end] ]>V[i]) end--;
           
           Q[++end]=i;
           if(V[Q[beg]]>max && i>=k) {max=V[Q[beg]]; p=i;}
          }
          
     
     printf("%d %d %d", p-k+1, p, max);
     
     //return 0;
}