Cod sursa(job #744419)

Utilizator vld7Campeanu Vlad vld7 Data 8 mai 2012 17:46:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>
#include <queue>

using namespace std;

FILE *f=fopen("secventa.in","r");
FILE *g=fopen("secventa.out","w");

int MAXIM=-35000;
int n, k, a[500001];
priority_queue<int, vector<int>, greater<int> > Q;

int main()
{
	int i, j, begin, end;
	
	fscanf(f,"%d%d", &n, &k);
	for(i=1; i<=n; i++)
		fscanf(f,"%d", &a[i]);
	begin=1; end=k;
	
	for(i=1; i<=k; i++)
	{
		Q.push(a[i]);
		if( Q.top()> MAXIM)
			MAXIM=Q.top();
	}
	
	for(i=k+1; i<n; i++)
	{
		if( a[i]>Q.top() )
		{
			begin++;	end++;
			Q.pop();
			Q.push(a[i]);
			MAXIM=Q.top();
		}
		else
		{
			while( !Q.empty() )
				Q.pop();
			for(j=i+1; j<=i+k; j++)
			{
				Q.push(a[j]);
				if( Q.top()> MAXIM)
				{
					MAXIM=a[j];
					begin=i+1; end=i+k;
				}
			}
			i+=k;
		}
	}
	
	Q.push(a[n]);
	if( Q.top() > MAXIM )
	{
		MAXIM=Q.top();
		end=n;
	}
	
	fprintf(g,"%d %d %d\n", begin, end, MAXIM);
	
	fclose(f);
	fclose(g);
	
	return 0;
}