Pagini recente » Cod sursa (job #1732531) | Cod sursa (job #542264) | Cod sursa (job #1938247) | Cod sursa (job #2432466) | Cod sursa (job #3040187)
/// [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;
}