Cod sursa(job #2210360)

Utilizator berindeiChesa Matei berindei Data 6 iunie 2018 13:09:28
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
int const NMAX=500000+10;

int v[NMAX], st[NMAX], sf[NMAX];
stack<int> stiva;
int n;

template <class T>
void clstack(stack<T>& stiva){
    while (!stiva.empty()) stiva.pop();
}

void calcst(){
    v[0]=-1e5;
    clstack(stiva);
    stiva.push(0);
    for (int i=1; i<=n; i++){
        while (v[stiva.top()]>=v[i])
            stiva.pop();
        st[i]=stiva.top()+1;
        stiva.push(i);
    }
}

void calcsf(){
    v[0]=-1e5;
    clstack(stiva);
    stiva.push(0);
    for (int i=1; i<=n; i++){
        while (v[stiva.top()]>v[i]){
            sf[stiva.top()]=i-1;
            stiva.pop();
        }
        stiva.push(i);
    }
    while (v[stiva.top()]>-1e5){
        sf[stiva.top()]=n;
        stiva.pop();
    }
}

int lsecv(int x){
    return sf[x]-st[x]+1;
}

int main(){
    int k, valmax=-1e5, stmax, sfmax;
    in >> n >> k;
    for (int i=1; i<=n; i++)
        in >> v[i];
    calcsf();
    calcst();
//    for (int i=1; i<=n; i++)
//        cout << st[i] << ' ' << sf[i] << "\n";
    for (int i=1; i<=n; i++){
        if (lsecv(i)<k) continue;
        if (v[i]>valmax){
            valmax=v[i];
            stmax=st[i];
            sfmax=(i-st[i]+1>=k) ? i : k+st[i]-1;
        }
        else if (v[i]==valmax){
            if (st[i]<stmax){
                valmax=v[i];
                stmax=st[i];
                sfmax=(i-st[i]+1>=k) ? i : k+st[i]-1;
            }
        }
    }
    out << stmax << ' ' << sfmax << ' ' << valmax;
}