Cod sursa(job #199174)

Utilizator tvladTataranu Vlad tvlad Data 17 iulie 2008 13:11:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>

const int N = 500000;

int n, k, st, fi;
int a[N], s[N];
char buf[N*10];

void add ( int x ) {
	int p;
	for (p = fi; p >= st && s[p] > x; --p);
	fi = p+1;
	s[fi] = x;
}

int main() {
	freopen("secventa.in","rt",stdin);
	freopen("secventa.out","wt",stdout);
	scanf("%d %d\n",&n,&k);
	fgets(buf,N*10,stdin);
	for (int i = 0, j = 0; i < n; ++i) {
		for (; buf[j] != '-' && (buf[j] < '0' || buf[j] > '9'); ++j);
		int semn = 1;
		if (buf[j] == '-') {
			semn = -1;
			++j;
		}
		for (a[i] = 0; buf[j] >= '0' && buf[j] <= '9'; ++j) a[i] = a[i]*10+buf[j]-'0';
		a[i] *= semn;
	}
	
	st = 0;
	fi = -1;
	for (int i = 0; i < k; ++i) add(a[i]);
	int max = s[st], maxs = 0;
	for (int i = k; i < n; ++i) {
		if (a[i-k] == s[st]) ++st;
		add(a[i]);
		if (s[st] > max) {
			max = s[st];
			maxs = i-k+1;
		}
	}
	printf("%d %d %d\n",maxs+1,maxs+k,max);
	return 0;
}