Cod sursa(job #304115)

Utilizator Omega91Nicodei Eduard Omega91 Data 10 aprilie 2009 23:12:35
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <cstdio>
#include <deque>
using namespace std;

const int NMAX = 500000;

int main()
{
    int N, K, i, minInd, max = -30001, startInd;
    int a[NMAX];
    ifstream fin("secventa.in");
    freopen("secventa.out", "w", stdout);
    deque<int> D;
    fin >> N >> K;
    for (i = 0; i < K - 1; ++i) {
        fin >> a[i];
        while (!D.empty() && a[D.back()] > a[i]) D.pop_back();
        D.push_back(i);
    }
    for (; i < N; ++i) {
        fin >> a[i];
        if (i - D.front() == K) D.pop_front();
        while (!D.empty() && a[D.back()] > a[i]) D.pop_back();
        D.push_back(i);
        minInd = D.front();
        if (a[minInd] > max) {
            max = a[minInd];
            startInd = minInd;
        }
    }
    int i1, i2;
    for (i1 = startInd; (i1 >= 0) && (a[i1] >= max); --i1);
    for (i2 = startInd; i2 != N && a[i2] >= max; ++i2);
    printf("%d %d %d\n", i1 + 2, i2, max);
    return 0;
}