Cod sursa(job #2579073)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 11 martie 2020 21:52:56
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<queue>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
const int NMax = 500000;
deque <int> Q;
pair <int, int> Sol;
int N, K, A[NMax+5];

void Solve() {
    Sol.first = -1e9;
    for (int i = 1; i <= N; i++) {
        while (!Q.empty() && A[i] < A[Q.back()])
            Q.pop_back();
        Q.push_back(i);
        if (!Q.empty() && Q.front() <= i-K)
            Q.pop_front();
        if (!Q.empty() && i >= K)
            if (A[Q.front()] > Sol.first)
                Sol.first = A[Q.front()], Sol.second = i;

    }
    out << Sol.second-K+1 << " " << Sol.second << " " << Sol.first << '\n';
}

int main() {
    in >> N >> K;
    for (int i = 1; i <= N; i++)
        in >> A[i];
    Solve();
}