Cod sursa(job #2033690)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 7 octombrie 2017 10:04:40
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <deque>

using namespace std;

int n, k;
int sir[5000005];
int valMin, pos;

void solve(){
    scanf("%d %d", &n, &k);

    for(int i = 0; i < n; i++){
        scanf("%d", &sir[i]);
    }

    deque<int> dq;

    for(int i = 0; i < k; i++){
        while(dq.size() > 0 && sir[dq.back()] > sir[i]){
            dq.pop_back();
        }
        dq.push_back(i);
    }

    valMin = sir[dq.front()];
    pos = 0;

    for(int i = k; i < n; i++){
        while(dq.front() < i - k + 1){
            dq.pop_front();
        }

        while(dq.size() > 0 && sir[dq.back()] > sir[i]){
            dq.pop_back();
        }

        dq.push_back(i);

        if(sir[dq.front()] > valMin){
            valMin = sir[dq.front()];
            pos = i - k + 1;
        }
    }

    printf("%d %d %d", pos + 1, pos + k, valMin);
}

int main() {
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    solve();

    return 0;
}