Cod sursa(job #1257009)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 7 noiembrie 2014 08:52:05
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <deque>
#define MAXN 500000
using namespace std;

deque <int> minim;
int v[MAXN];

int main () {
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");

    int n, k;
    cin >> n >> k;
    
    int max = -1, stop;
    for (int i = 0 ; i < n ; ++i) {
        cin >> v[i];
        
        if (!minim.empty() && i - minim.front() >= k)
            minim.pop_front();
        
        while (!minim.empty() && v[i] <= v[minim.back()])
           minim.pop_back();

        minim.push_back(i);
        
        if (i + 1 >= k && v[minim.front()] > max) {
           max = v[minim.front()];
           stop = i;
        }
    } 

    cout << stop - k + 2 << " " << stop + 1 << " " << max;

    return 0;
}