Cod sursa(job #332239)

Utilizator xaphariusMihai Suteu xapharius Data 17 iulie 2009 01:53:07
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
using namespace std;

#define max_str 3500001

int n, k;
vector<int> v, dq;
char s[max_str];

void citire(){
	scanf("%d%d", &n, &k);
	gets(s);	
	gets(s);

	int i = 0, num, sgn;
	v.push_back(0);
again:
	for(; !(s[i] >= '0' && s[i] <= '9'); ++i);
	
	if (s[i-1] == '-') sgn = -1;
	else sgn = 1;
	
	num = 0;
	for (; s[i] >= '0' && s[i] <= '9'; ++i) num = num * 10 + (s[i] - '0');
	num *= sgn;

	v.push_back(num);
	if ((int)v.size() - 1 < n) goto again;
}

void solve(){
	int st =0, dr = -1;
	int max = -300001, maxi, maxj;
	for (int i = 1; i < (int) v.size(); ++i){
		
		while (st <= dr && v[i] <= v[dq[dr]]){
			dq.pop_back();
			--dr;
		}
		
		dq.push_back(i);
		++dr;

		if (dq[st] == i - k) ++st;

		if ((i >= k) && (v[dq[st]] > max)) {
			max = v[dq[st]];
			maxi = i - k + 1;
			maxj = i;
		}
	}
	printf("%d %d %d", maxi, maxj, max);
}

int main(){
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	citire();
	solve();
	return 0;
}