Cod sursa(job #362668)

Utilizator Addy.Adrian Draghici Addy. Data 10 noiembrie 2009 17:07:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <string.h>
#define Nmax 500002
#define INF 1<<30

int A[Nmax], Deq[Nmax];
int n, k, i, semn, x, ok, p, u, sol, solp, solu;
char S[Nmax * 10];

int main() {
	
	FILE *f = fopen("secventa.in", "r");
	FILE *g = fopen("secventa.out", "w");
	
	fscanf(f, "%d %d\n", &n, &k);
	fgets(S, Nmax*10, f);
	u = strlen(S);
	
	for (i = 0, semn = 1; i < u; i++) {
		x = 0, ok = 0;
		if (S[i] == '-')
			semn = -1;
		while (S[i] >= '0' && S[i] <= '9' && i < u) {
			x = x * 10 + (S[i] - 48);
			ok = 1;
			i++;
		}
		if (ok)
			A[++p] = x * semn, semn = 1;
	}
	
	p = 1, u = 0, sol = -INF;
	for (i = 1; i <= n; i++) {
		while (p <= u && A[i] <= A[ Deq[u] ]) u--;
		
		Deq[++u] = i;
		
		if (Deq[p] == i-k) p++;
		
		if (i >= k && A[ Deq[p] ] > sol)
			sol = A[ Deq[p] ], solp = Deq[u]-k+1, solu = Deq[u];
	}
	
	fprintf(g, "%d %d %d", solp, solu, sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}