Cod sursa(job #3304015)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 19 iulie 2025 18:44:45
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <deque>
using namespace std;

const int NMAX = 500001;
int v[NMAX];

int main() {
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }

    deque<int> dq;
    int max_baza = -30001;
    int best_st = 1, best_dr = k;

    for (int i = 1; i <= n; i++) {
        // eliminăm elementele mai mari sau egale din coada din spate
        while (!dq.empty() && v[dq.back()] >= v[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // scoatem din față dacă a ieșit din fereastra [i-k+1, i]
        if (dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // verificăm doar când avem fereastra completă (lungime k)
        if (i >= k) {
            int current_baza = v[dq.front()];
            int st = i - k + 1;
            int dr = i;
            if (current_baza > max_baza ||
                (current_baza == max_baza && st < best_st) ||
                (current_baza == max_baza && st == best_st && dr < best_dr)) {
                max_baza = current_baza;
                best_st = st;
                best_dr = dr;
                }
        }
    }

    printf("%d %d %d\n", best_st, best_dr, max_baza);
    return 0;
}