Cod sursa(job #3040187)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 29 martie 2023 14:47:09
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
const int inf = 0x3f3f3f3f;

// cautam cu un deque minimul pentru secventele de lungime k
// iar apoi cu ajutorul unui stack incercam sa extindem in
// ambele sensuri secventa -> complexitate O(n)

const int nmax = 5e5;
int n, k;
int v[nmax + 1];
int small[nmax + 1]; // indicele cu valoarea minima din intervalul [i - k + 1, i]
int nse[nmax + 1]; // next smaller element
int lse[nmax + 1]; // last smaller element

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	fin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		fin >> v[i];
	}
	deque<int> dq;
	for (int i = 1; i <= n; ++i) {
		while (dq.size() && i - dq.front() >= k) {
			dq.pop_front();
		}
		while (dq.size() && v[dq.back()] > v[i]) {
			dq.pop_back();
		}
		dq.push_back(i);
		small[i] = dq.front();
	}
	stack<int> st;
	fill(nse + 1, nse + nmax + 1, n + 1);
	for (int i = 1; i <= n; ++i) {
		while (st.size() && v[st.top()] > v[i]) {
			nse[st.top()] = i, st.pop();
		}
		st.push(i);
	}
	while (st.size()) { st.pop(); }
	fill(lse + 1, lse + nmax + 1, 0);
	for (int i = n; i >= 1; --i) {
		while (st.size() && v[st.top()] > v[i]) {
			lse[st.top()] = i, st.pop();
		}
		st.push(i);
	}
	int l = 0, r = 0, ans = -inf;
	for (int i = k; i <= n; ++i) {
		if (ans < v[small[i]]) {
			ans = v[small[i]];
			l = lse[small[i]] + 1;
			r = nse[small[i]] - 1;
		}
	}
	fout << l << ' ' << r << ' ' << ans;
}