Cod sursa(job #48272)

Utilizator RazvanSSavu Razvan RazvanS Data 4 aprilie 2007 16:38:16
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#define Nmax 500001
#define MAX 3000001

using namespace std;

int V[Nmax], Q[Nmax];
char buffer[MAX];
int p;

void ins(int &x)
    {x=0;
     int k=buffer[p]=='-'?p++, k=-1 : k=1;
     for( ; buffer[p]>='0' && buffer[p]<='9' ; p++)
             x = x*10 + buffer[p] - '0';
     x*=k;    
    }         
              

int main(void)
    {int n, k;
     freopen("secventa.in", "r", stdin);
     freopen("secventa.out", "w", stdout);
     fread(buffer, 1, MAX, stdin);
     ins(n);
     p++;
     ins(k);
     p++;
         
     int i, ind=1;
     for(i=1;i<=n;i++)
         {ins(V[i]);
          p++;
         } 
              
       
     
     int max=-Nmax, p=0;
     int end=0, beg=1;
     
     
     //printf("%d\n", V[1]);
     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\n", V[Q[beg]]);
          }
          
     
     printf("%d %d %d\n", p-k+1, p, max);
     
     return 0;
}