Cod sursa(job #3226831)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 22 aprilie 2024 21:30:52
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[500005];
deque <pair<int,int>> d;

int main()
{
    int n,x,Max = -999999999,m,dr = 0,h;
    fin >> n >> m;
    for (int i=1;i<=n;++i){
        fin >> v[i];
    }
    for (int k=m;k<=n;++k){
        d.empty();
        for (int i=1;i<=n;++i){
            x = v[i];
            while (!d.empty() and i-d.front().second>=k) d.pop_front();
            while (!d.empty() and d.back().first>=x) d.pop_back();
            d.push_back({x,i});
            if (i>=k){
                if (Max<=d.front().first){
                    Max = d.front().first;
                    dr = i;
                    h = k;
                }
            }
        }
    }
    fout << dr-h+1 << ' ' << dr << ' ' << Max;
    return 0;
}