Cod sursa(job #1409820)

Utilizator stefanzzzStefan Popa stefanzzz Data 30 martie 2015 18:49:03
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <deque>
#define MAXN 500005
#define INF 2000000000
using namespace std;

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

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

	int i;
	
	scanf("%d %d", &n, &k);
	for(i = 1; i <= n; i++)
		scanf("%d", &v[i]);

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