Cod sursa(job #2869736)

Utilizator livliviLivia Magureanu livlivi Data 11 martie 2022 19:50:23
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <deque>

using namespace std;

const int N = 500000;
int v[N + 1];

deque<pair<int, int>> deq; // {valoare, pozitia} 
void insert_elem(int valoare, int pozitie) {
	while (!deq.empty() && deq.back().first >= valoare) {
		deq.pop_back();
	}
	deq.push_back({valoare, pozitie});
}

int main() {
	ifstream cin("secventa.in");
	ofstream cout("secventa.out");
	// citire
	int n, k; cin >> n >> k;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	// primele k elemente
	for (int i = 0; i < k; i++) {
		insert_elem(i);
	}

	int maxim = deq.front().first;
	int dr = k;
	for (int i = k; i < n; i++) {
		if (deq.front().second == i - k) {
			deq.pop_front();
		}
		insert_elem(v[i], i);
		
		if (deq.front().first > maxim) {
			maxim = deq.front().first;
			dr = i + 1;
		}
	}

	cout << dr - k + 1 << " " << dr << " " << maxim << "\n";
	return 0;
}