Cod sursa(job #3269453)

Utilizator deliaandreeaddelia andreea deliaandreead Data 19 ianuarie 2025 12:23:00
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

int v[500005];
deque<int>dq;

int main()
{
    int n,k;
    fin>>n>>k;
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    int baza=-30000, st=0, fi=0;
    dq.push_back(1);//eu bag in coada pozitiile numerelor din v, nu val lor
    for(int i=2;i<=n;i++){
        while(v[dq.back()]>v[i] && !dq.empty()){//tai din spate pana cand devine cresc sirul
            dq.pop_back();
        }
        dq.push_back(i);
        if(dq.front()<i-k+1){//tai din fata orice a "expirat"
            dq.pop_front();
        }
        if(i>=k && baza<v[dq.front()]){//fac maximul dintre minime(care sunt mereu in fata dq ului)
            baza=v[dq.front()];
            st=i-k+1;
            fi=i;
            //cout<<i-k+1<<" "<<i<<" "<<baza<<endl;
        }
    }
    fout<<st<<" "<<fi<<" "<<baza;

    return 0;
}