Cod sursa(job #749453)

Utilizator iris88Nagy Aliz iris88 Data 17 mai 2012 10:11:13
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <list>
#include <limits.h>
using namespace std;
typedef struct elem{
	int key,index;
}elem;
elem Q[500001];

int secv[500001];
int main()
{
	FILE *f=fopen("secventa.in","r");
	int n,k;
	fscanf(f,"%d %d",&n,&k);
	for (int i=0;i<n;i++)
	{
		fscanf(f,"%d",&secv[i]);
	}
	fclose(f);
	int ind2=0;
	int ind1=0;
	Q[ind2].index = 0;Q[ind2].key = secv[0];
	ind2++;
	int maxi=0,maxim=INT_MIN;
	for (int i=1;i<n;i++)
	{
		while (ind2>ind1 && Q[ind2-1].key>secv[i])
			ind2--;
		Q[ind2].key =secv[i];Q[ind2].index = i;
		ind2++;
		while (Q[ind1].index<i-k+1)
			ind1++;
		if (i>k-2 && Q[ind1].key>maxim){
			maxi = i-k+2;
			maxim = Q[ind1].key;
		}
	}
	FILE *g = fopen("secventa.out","w+");
	fprintf(g,"%d %d %d\n",maxi,maxi+k-1,maxim);
	fclose(g);
	return 0;
}