Cod sursa(job #91877)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 13 octombrie 2007 17:41:53
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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, j, u;
	char buf[8];

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

	for (i = 0; i < N; ++i) {
//		fscanf(fin, " %d", A + i);
		fscanf(fin, " %s", buf);
		for (j = 0, u = 0; '0' <= buf[j] && buf[j] < '9'; ++j)
			u = u * 10 + (buf[j] - '0');
		A[i] = u;
	}

	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 = i;
	}
}

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

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

	fclose(fout);
}

int main(void) {

	read();

	solve();

	write();

	return 0;
}