Pagini recente » Cod sursa (job #51132) | Cod sursa (job #1378269) | Cod sursa (job #2570013) | Cod sursa (job #2714988) | Cod sursa (job #2420055)
#include <fstream>
#include <vector>
#include <stack>
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(N_MAX), rightI(N_MAX);
int sol { -(1 << 30) }, solStart, solEnd;
int getInt() {
char c;
while (isspace(c = in.get()));
int sol { 0 }, coef { 1 };
if (c == '-') {
coef = -1;
c = in.get();
}
while (isdigit(c)) {
sol = sol * 10 + c - '0';
c = in.get();
}
return sol * coef;
}
void init() {
ios_base::sync_with_stdio(false);
in.tie(0);
N = getInt();
K = getInt();
for (int i { 1 }; i <= N; ++i)
a[i] = getInt();
stack<int> st;
for (int i { 1 }; i <= N; ++i) {
while (!st.empty() && a[st.top()] > a[i]) {
rightI[st.top()] = i;
st.pop();
}
if (!st.empty())
leftI[i] = st.top();
st.push(i);
}
}
void solve() {
for (int i { 1 }; i <= N; ++i) {
if (!rightI[i])
rightI[i] = N + 1;
if (rightI[i] - 1 - leftI[i] < K || a[i] < sol)
continue;
int l { i - leftI[i] <= K ? leftI[i] + 1 : i - K + 1 }, r { l + K - 1 };
if (a[i] > sol || (a[i] == sol && l < solStart) || (a[i] == sol && l == solStart && r < solEnd)) {
sol = a[i];
solStart = l;
solEnd = r;
}
}
}
void print() {
out << solStart << ' ' << solEnd << ' ' << sol;
}
int main() {
init();
solve();
print();
}