Cod sursa(job #2482271)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 27 octombrie 2019 23:18:48
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;

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

struct Triplet {
    int x, y, z;
    Triplet(int x, int y, int z)
        : x(x), y(y), z(z) { }
    inline bool operator<(Triplet t) const {
        return x > t.x || (x == t.x && (y < t.y || (y == t.y && z < t.z)));
    }
};

class Deque {
  private:
    int len, cnt;
    deque<pair<int, int>> dq;

  public:
    Deque(int len) {
        this->len = len;
        cnt = 0;
    }

    void insert(int x) {
        while (!dq.empty() && dq.back().first >= x)
            dq.pop_back();
        dq.emplace_back(x, ++cnt);
        if (dq.front().second == cnt - len)
            dq.pop_front();
    }

    int query() {
        return dq.front().first;
    }
};

int main() {
    int n, k;
    fin >> n >> k;

    Deque dq(k);
    Triplet sol(-1e9, 0, 0);

    for (int i = 1; i <= n; i++) {
        int x; fin >> x;
        dq.insert(x);
        if (i >= k)
            sol = min(sol, Triplet(dq.query(), i - k + 1, i));
    }
    fout << sol.y << ' ' << sol.z << ' ' << sol.x << '\n';

    fout.close();
    return 0;
}