Cod sursa(job #3272611)

Utilizator deliaandreeaddelia andreea deliaandreead Data 30 ianuarie 2025 11:00:31
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 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(!dq.empty() && v[dq.back()]>v[i]){//tai din spate pana cand devine cresc sirul
            dq.pop_back();
        }
        dq.push_back(i);
        while( !dq.empty() && dq.front()<i-k+1){//tai din fata orice a "expirat"
            dq.pop_front();
        }
        if( i>=k ){//fac maximul dintre minime(care sunt mereu in fata dq ului)
            if (v[dq.front()]>baza) {
                baza=v[dq.front()];
                st=i-k +1;
                fi=i;
            }
        }
    }
    if(n>1)
        fout<<st<<" "<<fi<<" "<<baza;
    else
        fout<<1<<" "<<1<<" "<<v[1];

    return 0;
}