Cod sursa(job #362620)

Utilizator Addy.Adrian Draghici Addy. Data 10 noiembrie 2009 14:14:39
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <stdio.h>
#define Nmax 500003
#define INF 1<<30

struct deque {
	int poz; int v;
};

deque Deq[Nmax];
int v[Nmax];
int N, K, i, p, u, sol, solp, solu;

int main() {
	
	FILE *f = fopen("secventa.in", "r");
	FILE *g = fopen("secventa.out", "w");
	
	fscanf(f, "%d %d", &N, &K);
	for (i = 1; i <= N; i++)
		fscanf(f, "%d", &v[i]);
	
	p = 1, u = 0, sol = -INF;
	for (i = 1; i <= N; i++) {
		while (p <= u && Deq[u].v > v[i]) u--;
		
		u++, Deq[u].poz = i, Deq[u].v = v[i];
		
		if (Deq[p].poz == i-K) p++;
		if (i >= K)
			if (Deq[p].v > sol)
				sol = Deq[p].v, solp = Deq[p].poz, solu = Deq[u].poz;
	}
	
	fprintf(g, "%d %d %d", solp, solu, sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}