Cod sursa(job #2418816)

Utilizator SemetgTemes George Semetg Data 6 mai 2019 15:56:44
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#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();
}