Cod sursa(job #2033748)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 7 octombrie 2017 10:24:34
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;

#define NMAX 500005

int n, k, a[NMAX];
deque<int> deq;
int baza_max, inc, sf;

void citire() {
	scanf("%d %d ", &n, &k);
	for_each(a + 1, a + n + 1, [](int &x) { scanf("%d", &x);});
}

void rezolvare() {
	deq.push_back(1);

	for(int i = 2; i <= k; i++) {
		while(!deq.empty() && a[i] < a[deq.back()])
			deq.pop_back();

		deq.push_back(i);
	}

	for(int i = k; i <= n; i++) {
		while(!deq.empty() && deq.front() <= i - k) 
			deq.pop_front();

		while(!deq.empty() && a[i] < a[deq.back()])
			deq.pop_back();

		deq.push_back(i);

		if(a[deq.front()] > baza_max && i >= k - 1) {
			inc = deq.front();
			sf = deq.back();
			baza_max = a[deq.front()];
		}
	}
}

void afisare() {
	printf("%d %d %d\n",inc, sf, baza_max);
}

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

	citire();

	rezolvare();

	afisare();

	return 0;
}