Cod sursa(job #531207)

Utilizator mvbinfoDragos Dinca mvbinfo Data 9 februarie 2011 10:32:20
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<stdio.h>
#define dim 500005
using namespace std;

int A[dim],n,k,i,max=-dim,deque[dim],front,back,ii;

int main()
{
	FILE *f=fopen("secventa.in","r"), *g=fopen("secventa.out","w");
	
fscanf(f,"%d %d",&n,&k);

for(i=1;i<=n;i++)
	fscanf(f,"%d",&A[i]);

front=1;
back=0;

for(i=1;i<=n;i++)
{
	while(front <= back && A[ i ] <= A[ deque[ back ] ] )
		back--;
	
	deque[++back]=i;
	
	if(deque[ front ] == i-k) 
		front++;
	
	if(i>=k && A[ deque[ front ] ] > max )
		{
			max=A[ deque[ front ] ];
			ii=i-k+1;
		}
}
fprintf(g,"%d %d %d\n",ii,ii+k-1,max);

fclose(f);
fclose(g);
return 0;
}