Cod sursa(job #1409836)

Utilizator stefanzzzStefan Popa stefanzzz Data 30 martie 2015 18:56:22
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <deque>
#define MAXN 500005
#define INF 2000000000
#define MAXC (1 << 16)
using namespace std;

int n, v[MAXN], k, sol = -INF, solr, cnt;
deque<int> dq;
char buf[MAXC];

inline int getInt(){
	while((buf[cnt] < '0' || buf[cnt] > '9') && buf[cnt] != '-'){
		if(++cnt == MAXC){
			cnt = 0;
			fread(buf, 1, MAXC, stdin);
		}
	}

	int x = 0, sign = 1;
	
	if(buf[cnt] == '-'){
		sign = -1;
		if(++cnt == MAXC){
			cnt = 0;
			fread(buf, 1, MAXC, stdin);
		}
	}

	while(buf[cnt] >= '0' && buf[cnt] <= '9'){
		x = x * 10 + buf[cnt] - '0';
		if(++cnt == MAXC){
			cnt = 0;
			fread(buf, 1, MAXC, stdin);
		}
	}

	return sign * x;
}


int main(){
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);

	int i;
	
	fread(buf, 1, MAXC, stdin);

	n = getInt(); k = getInt();
	for(i = 1; i <= n; i++)
		v[i] = getInt();

	for(i = 1; i < k; i++){
		while(!dq.empty() && v[i] <= v[dq.back()])
			dq.pop_back();
		dq.push_back(i);
	}

	for(i = k; i <= n; i++){
		while(!dq.empty() && v[i] <= v[dq.back()])
			dq.pop_back();
		dq.push_back(i);
		while(dq.front() <= i - k) dq.pop_front();
		if(v[dq.front()] > sol){
			sol = v[dq.front()];
			solr = i;
		}
	}

	printf("%d %d %d\n", solr - k + 1, solr, sol);
	
	return 0;
}