Cod sursa(job #1632115)

Utilizator AureliaCretu Aurelia Aurelia Data 5 martie 2016 21:34:43
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n, k, v[500001], i;
deque <int> deq;
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() {

    f>>n>>k;

    int maxF = -100000000;
    int maxI = 0;
    int maxE = 0;

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

       f>>v[i];
        ins(i);
        rem(i);

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

    }
g<<maxI<<" "<<maxE<<" "<<maxF;
g.close();
f.close();
return 0;
}