Cod sursa(job #47596)

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

using namespace std;

int V[Nmax], Q[Nmax]; 

int main(void)
    {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\n", p-k+1, p, max);
     
     return 0;
}