Cod sursa(job #304119)

Utilizator Omega91Nicodei Eduard Omega91 Data 10 aprilie 2009 23:19:04
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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) && (startInd - i1 + 1 <= K); --i1);
    i1++;
    for (i2 = startInd; (i2 != N) && (a[i2] >= max) && (i2 - i1 + 1 <= K); ++i2);
    i2--;
    printf("%d %d %d\n", i1 + 1, i2 + 1, max);
    return 0;
}