Cod sursa(job #2914600)

Utilizator db_123Balaban David db_123 Data 20 iulie 2022 14:32:36
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

ifstream cin("secventa.in");
ofstream cout("secventa.out");

int n,k;
vector<int> v;
deque<int> dq;

void read(){
    cin>>n>>k;
    v.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
}

void solve(){
    int r=k,res=0,currMin,l=1;
    int posS,posE;
    for(int r=1;r<=n;r++){
        while(!dq.empty() && v[dq.back()]>v[r]){
            dq.pop_back();
        }
        dq.push_back(r);
        currMin=v[dq.front()];
        while(l<=n && r-l+1>=k){
            if(res<v[dq.front()]){
                posS=l;
                posE=r;
                res=v[dq.front()];
            }
            else if(res==v[dq.front()]){
                if(posS>l){
                    posS=l;
                    posE=r;
                }
                else if(posS==l && posE<r){
                    posE=r;
                }
            }
            // res=max(res,v[dq.front()]);
            currMin=v[dq.front()];
            if(dq.front()<=l){
                dq.pop_front();
            }
            l++;
        }
    }
    cout<<posS<<" "<<posE<<" "<<res;
}

int main(){
    
    read();
    solve();
    return 0;
}