Cod sursa(job #3189776)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 6 ianuarie 2024 14:52:56
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <stack>
#include <vector>
#include <climits>
#define N 500001
std::ifstream fin("input.in");
std::ofstream fout("output.out");
std::stack<int> S;
int arr[N];
std::vector<int> nxtGreater(int inv, int n){
    std::vector<int> ans(n + 1, 0);
    if(inv == 1){
        for(int i = 1; i <= n; i++){
            if(S.empty()){
                S.push(i); continue;
            }
            while(!S.empty() && arr[i] < arr[S.top()]){
                ans[S.top()] = i;
                S.pop(); 
            }
            S.push(i);
        }
        while(S.empty() == false){
            ans[S.top()] = n + 1;
            S.pop();
        }
    }
    else{
        for(int i = n; i >= 1; i--){
            if(S.empty()){
                S.push(i); continue;
            }
            while(!S.empty() && arr[i] < arr[S.top()]){
                ans[S.top()] = i;
                S.pop(); 
            }
            S.push(i);
        }
        while(S.empty() == false){
            ans[S.top()] = 0;
            S.pop();
        }
    }
    return ans;
}
int main(){
    int n, k;
    fin >> n >> k;
    for(int i = 1; i <= n; i++){
        fin >> arr[i];
    }
    std::vector<int> ans1 = nxtGreater(1, n);
    std::vector<int> ans2 = nxtGreater(2, n);
    int mx = INT_MIN, left, right;
    for(int i = 1; i <= n; i++){
        int curr_size = 0;
        curr_size += ans1[i] - i - 1;
        curr_size += i - ans2[i];
        if(curr_size >= k){
            if(mx < arr[i])
                mx = arr[i], left = ans2[i] + 1, right = ans1[i] - 1;
        }
    }
    fout << left << " " << right << " " << mx;
}