Cod sursa(job #937450)

Utilizator ericptsStavarache Petru Eric ericpts Data 10 aprilie 2013 13:37:31
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <deque>
#include <iostream>

using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");

#define push push_back
#define rm_front() while(!Q.empty() && Q.front() < i - k + 1)Q.pop_front()
#define rm_back() while(!Q.empty() && v[Q.back()] >= v[i])Q.pop_back()

const int maxn = 500100;
short v[maxn];
int n,k;
deque<int> Q;
int best = -(1<<30),st,fin;

int main()
{
    in >> n  >> k;
    int i;for(i = 1 ; i <= n ; ++ i){
        in >> v[i];
        rm_front();
        rm_back();
        Q.push(i);

        if(v[Q.front()] > best && i >= k){
            fin = i;
            st = min(i-k+1,Q.front());
            best = v[Q.front()];
        }
    }
    out << st << " " << fin << " " << best << "\n";
    return 0;
}