Cod sursa(job #444841)

Utilizator HoriaClementHoriaC HoriaClement Data 21 aprilie 2010 20:52:35
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>

#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,end=0,beg=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 %d %d\n", p-k+1, p, max);
     return 0;
}