Cod sursa(job #3211201)

Utilizator susanEmily Susan susan Data 8 martie 2024 18:44:11
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#pragma GCC optimize("O3,unroll-loops")

#include <fstream>
#include <iostream>
#include <deque>
#include <limits>

using namespace std;

int fp() {
    int ch, t = 1, n = 0;
    while ((ch = getchar_unlocked()) && !isdigit(ch) && ch != '-');

    if (ch == '-')
        t = -1;

    if (isdigit(ch))
        n = ch - '0';

    while ((ch = getchar_unlocked()) && isdigit(ch))
        n = n * 10 + ch - '0';

    return t * n;
}

int main() {
    freopen("secventa.in", "r", stdin);
    ofstream g("secventa.out");
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = fp(), k = fp(), baza = numeric_limits<int>::min(), j = -1;

    deque<pair<int, int>> Q;
    for (int i = 1, x; i <= n; ++i) {
        x = fp();

        while (!Q.empty() && Q.back().first > x)
            Q.pop_back();
        Q.emplace_back(x, i);

        if (!Q.empty() && Q.front().second == i - k)
            Q.pop_front();

        if (!Q.empty() && i >= k && Q.front().first > baza) {
            baza = Q.front().first;
            j = i;
        }
    }

    g << j - k + 1 << ' ' << j << ' ' << baza << '\n';
}