Cod sursa(job #2707924)

Utilizator ValiAntonieAntonie Valentin ValiAntonie Data 17 februarie 2021 23:00:25
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

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

stack <pair<int,int>> S;
int n,v[500001],i,dr[500001],st[500001],x,Max,k,a,b;
int main()
{
fin>>n>>k;
for(i=1;i<=n;i++)
    fin>>v[i];
for(i=1;i<=n;i++){
    x = v[i];
    while(S.empty() == false && x<S.top().first){
        dr[S.top().second] = i;
        S.pop();
    }
    S.push({x,i});
}
while(S.empty() == false){
    S.pop();
}
for(i=n;i>=1;i--){
    x = v[i];
    while(S.empty() == false && x < S.top().first){
        st[S.top().second] = i;
        S.pop();
    }
    S.push({x,i});
}
for(i=1;i<=n;i++){
    if(!dr[i])
    dr[i] = n + 1;
    if(dr[i] - st[i] - 1 >= k && v[i] == Max){
        if(st[i] < a){
            a = st[i];
            b = dr[i];
        }
        else if(st[i] == a && dr[i] < b){
            a = st[i];
            b = dr[i];
        }
    }
    if(dr[i] - st[i] - 1 >= k && v[i] > Max){
        Max = v[i];
        a = st[i];
        b = dr[i];
    }
}
fout << a + 1<< " " << b - 1<< " " << Max;

    return 0;
}