Pagini recente » Cod sursa (job #2657509) | Cod sursa (job #696921) | Cod sursa (job #2150789) | Cod sursa (job #2358337) | Cod sursa (job #2418816)
#include <fstream>
#include <vector>
using namespace std;
const string FILE_NAME = "secventa";
const int N_MAX { 500005 };
ifstream in { FILE_NAME + ".in" };
ofstream out { FILE_NAME + ".out" };
int N, K;
vector<int> a(N_MAX), leftI, rightI;
int sol { -(1 << 30) }, solStart, solEnd;
void init() {
in >> N >> K;
for (int i { 1 }; i <= N; ++i)
in >> a[i];
vector<int> st;
rightI.assign(N_MAX, N + 1);
for (int i { 1 }; i <= N; ++i) {
while (!st.empty() && a[st.back()] > a[i]) {
rightI[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
st.clear();
leftI.assign(N_MAX, 0);
for (int i { N }; i >= 1; --i) {
while (!st.empty() && a[st.back()] > a[i]) {
leftI[st.back()] = i;
st.pop_back();
}
st.push_back(i);
}
}
void solve() {
for (int i { 1 }; i <= N; ++i) {
int length { rightI[i] - 1 - leftI[i] };
if (length < K || a[i] < sol)
continue;
int startLeft { i - max(K - (rightI[i] - i), 0) };
bool ok { false };
if (a[i] > sol) {
ok = true;
} else if (a[i] == sol && startLeft > leftI[i]) {
if (startLeft < solStart || (startLeft == solStart && startLeft + K - 1 < solEnd))
ok = true;
}
if (ok) {
sol = a[i];
solStart = startLeft;
solEnd = startLeft + K - 1;
}
}
}
void print() {
out << solStart << ' ' << solEnd << ' ' << sol;
}
int main() {
init();
solve();
print();
}