Cod sursa(job #1623387)

Utilizator razvandRazvan Dumitru razvand Data 1 martie 2016 19:12:18
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");
int v[500003];
deque<int> deq;
int n,k;

void ins(int val) {
    while(!deq.empty() && v[val] <= v[deq.back()])
        deq.pop_back();
    deq.push_back(val);
}

void rem(int val) {
    while(!deq.empty() && val-k >= deq.front())
        deq.pop_front();
}

int main() {

    in >> n >> k;
    int maxF = 0;
    int maxI = 0;
    int maxE = 0;

    for(int i = 1; i <= n; i++) {

        in >> v[i];
        ins(i);

        if(i >= k) {

            rem(i);

            if(v[deq.front()] > maxF) {

                maxF = v[deq.front()];
                maxI = i-k+1;
                maxE = i;

            }

        }

    }

    out << maxI << " " << maxE << " " << maxF;

    return 0;
}