Cod sursa(job #2770925)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 24 august 2021 10:18:23
Problema Secventa Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

const int mxN = 5e5 + 5;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int main() {
    ios::sync_with_stdio(false), fin.tie(nullptr);
    int N, K, nums[mxN]; fin >> N >> K;
    for (int i = 1; i <= N; ++i) {
        fin >> nums[i];
    }
    set<pair<int, int>> s;
    int best_first_pos = 1, best_end_pos = K, max_base = INT_MAX;
    for (int i = 1; i <= K; ++i) {
        max_base = min(max_base, nums[i]);
        s.insert({nums[i], i});
    }
    for (int i = K + 1; i <= N; ++i) {
        s.erase(s.find({nums[i - K], i - K}));
        s.insert({nums[i], i});
        if (max_base < s.begin()->first) {
            max_base = s.begin()->first;
            best_first_pos = i - K + 1;
            best_end_pos = i;
        }
    }
    fout << best_first_pos << " " << best_end_pos << " " << max_base;
    return 0;
}