Cod sursa(job #1454321)

Utilizator piroComisia piro Data 26 iunie 2015 02:05:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

int x[500001], q[500001];

class IOReader {
    public:
        IOReader() {
            bufferSize = 4096;
            pos = 4096;
        }

        void readInt(int &res) {
            int sign = 1;
            char ch;
            res = 0;
            do {
                ch = getChar();
                if (ch == '-')
                    sign = -1;
            } while (!isdigit(ch));
            do {
                res = res * 10 + ch - '0';
                ch = getChar();
            } while (isdigit(ch));
            res = res * sign;
        }

    private:
        int bufferSize, pos;
        char buffer[4096];

        char getChar() {
            if (pos == bufferSize) {
                fread(buffer, 1, bufferSize, stdin);
                pos = 0;
            }
            return buffer[pos++];
        }
};

int main() {
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    int n, k;
    IOReader IO;
    IO.readInt(n);
    IO.readInt(k);
    for (int i = 1; i <= n; ++i)
        IO.readInt(x[i]);

    int p = 1, u = 0, res = -33333, ind;
    for (int i = 1; i <= n; ++i) {
        while (p <= u && x[i] < x[q[u]])
            --u;
        q[++u] = i;
        if (q[p] + k == i)
            ++p;
        if (x[q[p]] > res && i >= k) {
            res = x[q[p]];
            ind = i;
        }
    }

    printf("%d %d %d", ind - k + 1, ind, res);
    return 0;
}