Cod sursa(job #749452)

Utilizator iris88Nagy Aliz iris88 Data 17 mai 2012 10:06:04
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <list>
#include <limits.h>
using namespace std;
typedef struct elem{
	int key,index;
}elem;
list<elem*> Q;

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);
	elem* e0 = new elem;
	e0->index = 0;e0->key = secv[0];
	Q.push_back(e0);
	int maxi=0,maxim=INT_MIN;
	for (int i=1;i<n;i++)
	{
		while (!Q.empty() && Q.back()->key>secv[i])
			Q.pop_back();
		e0 = new elem;e0->key =secv[i];e0->index = i;
		Q.push_back(e0);
		while (!Q.empty() && Q.front()->index<i-k+1)
			Q.pop_front();
		if (i>k-2 && Q.front()->key>maxim){
			maxi = i-k+2;
			maxim = Q.front()->key;
		}
	}
	FILE *g = fopen("secventa.out","w+");
	fprintf(g,"%d %d %d\n",maxi,maxi+k-1,maxim);
	fclose(g);
}