Cod sursa(job #812502)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 13 noiembrie 2012 22:20:56
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <utility>
#include <queue>
#include <cstdio>
using namespace std;

// ifstream in("date.in");
// ofstream out("date.out");

FILE *in = fopen("secventa.in", "r"), *out = fopen("secventa.out", "w");

deque<pair<int,int> > q;
int n,k,a[500010],i,li,ls,m;

int main() {
    fscanf(in, "%d%d", &n, &k);
    m = -(1<<29);
    for(i=1; i<=n; i++) {
        fscanf(in, "%d", &a[i]);
        while(!q.empty() && q.back().first >= a[i]) {
            q.pop_back();
        }
        q.push_back(make_pair(a[i], i));
        while(q.front().second <= i-k) {
            q.pop_front();
        }
        if(i >= k && m < q.front().first) {
            m = q.front().first;
            li = i-k+1;
            ls = i;
        }
    }
    while(li > 1 && a[li-1] >= m)
        li--;
    fprintf(out, "%d %d %d", li, ls, m);
    return 0;
}