Cod sursa(job #1844238)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 ianuarie 2017 20:34:03
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

const int maxn = 5e5 + 5;
deque <int> D;
int V[maxn];

class Scanner {
public:
    inline Scanner& operator >> (int &val) {
        bool neg = false;
        while (!(Buff[i] >= '0' && Buff[i] <= '9')) {
            if (Buff[i] == '-') {
                neg = true;
            }
            Advance();
        }
        val = 0;
        while (Buff[i] >= '0' && Buff[i] <= '9') {
            val = (val << 1) + (val << 3) + (Buff[i] - '0');
            Advance();
        }
        if (neg == true) {
            val = -val;
        }
        return *this;
    }
private:
    char Buff[1 << 17];
    int i = (1 << 17) - 1;
    void Advance() {
        if (++i == (1 << 17)) {
            i = 0;
            f.read(Buff, 1 << 17);
        }
    }
} fin;

int main() {
    ios_base :: sync_with_stdio (false);
    int n, k, i, ans = -1e9, x, y;
    fin >> n >> k;
    for (i = 1; i <= n; i++) {
        fin >> V[i];
    }
    for (i = 1; i <= n; i++) {
        while (!D.empty() && V[D.back()] > V[i]) {
            D.pop_back();
        }
        D.push_back(i);
        if (D.front() == i - k) {
            D.pop_front();
        }
        if (V[D.front()] > ans && i >= k) {
            x = i - k + 1;
            y = i;
            ans = V[D.front()];
        }
    }
    fout << x << " " << y << " " << ans << "\n";
    f.close();
    fout.close();
    return 0;
}