Cod sursa(job #91874)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 13 octombrie 2007 17:33:45
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>

const int NMAX = 1 << 19;
const int INF = 0x3f3f3f3f;

int N, K;
int A[NMAX];
int Q[NMAX], poz[NMAX];
int mx, mpoz;

void read(void) {
	FILE *fin = fopen("secventa.in", "rt");
	int i;

	fscanf(fin, " %d %d", &N, &K);

	for (i = 0; i < N; ++i)
		fscanf(fin, " %d", A + i);

	fclose(fin);
}

void solve(void) {
	int i;
	int st, dr;

	st = 0; dr = -1;
	mx = -INF;
	for (i = 0; i < N; ++i) {
		
		while (st <= dr && poz[st] + K <= i) ++st;
		while (st <= dr && Q[dr] >= A[i]) --dr;

		++dr; Q[dr] = A[i]; poz[dr] = i;

//		printf("%d %d (%d, %d)\n", i, Q[st], st, dr);
		
		if (i + 1 >= K && mx < Q[st])
			mx = Q[st], mpoz = poz[st];
	}
}

void write(void) {
	FILE *fout = fopen("secventa.out", "wt");

	fprintf(fout, "%d %d %d\n", mpoz + 1, mpoz + K, mx);

	fclose(fout);
}

int main(void) {

	read();

	solve();

	write();

	return 0;
}