Cod sursa(job #2427505)

Utilizator PrekzursilAndrei Visalon Prekzursil Data 31 mai 2019 22:57:51
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#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;
void init() {
    ios_base::sync_with_stdio(false);
    in.tie(0);
    in >> N >> K;
    in.get();
    string line;
    getline(in, line);
    int index { 0 };
    for (int i { 1 }; i <= N; ++i) {
        while (isspace(line[index]))
            ++index;
        int coef { 1 };
        if (line[index] == '-') {
            ++index;
            coef = -1;
        }
        while (index < int(line.size()) && isdigit(line[index]))
            a[i] = a[i] * 10 + line[index++] - '0';
        a[i] *= coef;
    }
    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();
}