Cod sursa(job #2915818)

Utilizator db_123Balaban David db_123 Data 25 iulie 2022 11:56:34
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 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 l=1,r=1,currMin;
    int res=0;
    dq.push_back(1);
    int resS,resE;
    while(r<=n) {
        while(r<=n && r-l+1<k) {
            r++;
            while(!dq.empty() && v[dq.back()]>v[r]) {
                dq.pop_back();
            }
            dq.push_back(r);
        }
        if(r-l+1>=k) {
            if(res<v[dq.front()]) {
                res=v[dq.front()];
                resS=l;
                resE=r;
            }
            else if(res==v[dq.front()]) {
                if(l<resS) {
                    resS=l;
                    resE=r;
                }
                else if(l==resS && r<resE) {
                    r=resE;
                }
            }
            res=max(res,v[dq.front()]);
        }
        currMin=v[dq.front()];
        if(l<=r && v[dq.front()]<=currMin) {
            if(!dq.empty() && dq.front()<=l) {
                dq.pop_front();
            }
            l++;
        }
    }
    cout<<resS<<" "<<resE<<" "<<res;
}

int main() {

    read();
    solve();
    return 0;
}