Cod sursa(job #2504399)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 4 decembrie 2019 21:23:36
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <bits/stdc++.h>

FILE *in = fopen("secventa.in", "r"), *out = fopen("secventa.out", "w") ;

const int MV = 5e5 ;

int v[MV + 1] ;
int left[MV + 1] ;
int right[MV + 1] ;

void solveStiva(int n) {
        std::stack<int> stiva ;
        left[1] = 0 ;
        stiva.push(1) ;
        for (int i = 2 ; i <= n ; ++ i) {
                while (!stiva.empty() && v[stiva.top()] > v[i]) {
                        stiva.pop() ;
                }
                if (stiva.empty())
                        left[i] = 1 ;
                else left[i] = stiva.top() ;
                stiva.push(i) ;
        }
        std::stack<int> st ;
        right[n] = n + 1 ;
        st.push(n) ;
        for (int i = n - 1 ; i > 0 ; -- i) {
                while (!st.empty() && v[st.top()] > v[i]) {
                        st.pop() ;
                }
                if (st.empty())
                        right[i] = n + 1 ;
                else right[i] = st.top() ;
                st.push(i) ;
        }
}

int main() {
        int n, k ;
        fscanf(in, "%d %d", &n, &k) ;
        for (int i = 1 ; i <= n ; ++ i) {
                fscanf(in, "%d", v + i) ;
        }
        solveStiva(n) ;
        int bazaMax(0) ;
        int leftInt(0), rightInt(0) ;
        for (int i = 1 ; i <= n ; ++ i) {
                int length = (right[i] - 1) - (left[i] + 1) + 1;
                if (length >= k) {
                        if (v[i] == bazaMax) {
                                if (left[i] == leftInt) {
                                        if (right[i] < rightInt) {
                                                rightInt = right[i] ;
                                        }
                                } else if (left[i] < leftInt) {
                                        leftInt = left[i] ;
                                        rightInt = right[i] ;
                                }
                        } else if (v[i] > bazaMax) {
                                bazaMax = v[i] ;
                                leftInt = left[i] ;
                                rightInt = right[i] ;
                        }
                }
        }
        fprintf(out, "%d %d %d", leftInt + 1, rightInt - 1, bazaMax) ;
}