Cod sursa(job #3145334)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 14 august 2023 22:03:59
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 500001;
int n,k,st[NMAX],dr[NMAX],poz;
int main()
{
    fin >> n >> k;
    vector<int> v(n+1);
    stack<int> s;
    for(int i=1; i <= n; i++)
        fin >> v[i];
    for(int i=1; i <= n; i++)
    {
        while(!s.empty() && v[i] < v[s.top()]) {
            dr[s.top()] = i-1;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty())
        dr[s.top()] = n , s.pop();
    for(int i=n; i >= 1; i--) {
        while(!s.empty() && v[i] < v[s.top()]) {
            st[s.top()] = i + 1;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty())
        st[s.top()] = 1 , s.pop();
    int maxim = INT_MIN,cnt = 0;
    for(int i=1; i <= n; i++) {
        if(dr[i]-st[i]+1 >= k) {
            if(v[i] > maxim) {
                maxim = v[i];
                poz = i;
                cnt = 1;
            }
            else if(v[i] == maxim)
                cnt++;
        }
    }
    /*for(int i=1; i <= n; i++)
        cout << st[i] << ' ' << dr[i] << endl;
    return 0;*/
    int minim = INT_MAX,minim2=INT_MAX,poz1,poz2,poz3;
    if(cnt == 1) {
        fout << st[poz] << ' ' << dr[poz] << ' ' << maxim;
    }
    else {
        cnt = 1;
        for(int i=1; i <= n; i++) {
            if(dr[i]-st[i]+1 >= k && v[i] == maxim) {
                if(st[i] < minim) {
                    minim = st[i];
                    poz1 = i;
                    cnt = 1;
                    minim2 = dr[i];
                }
                else if(st[i] == minim) {
                    cnt++;
                    if(dr[i] < minim2) {
                        minim2 = dr[i];
                        poz1 = i;
                    }
                }
            }
        }
        fout << st[poz1] << ' ' << dr[poz1] << ' ' << maxim;
    }
    return 0;
}