Mai intai trebuie sa te autentifici.

Cod sursa(job #2482279)

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

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;
    }
};

class Parser {
  private:
    static const int SIZE = 100000;

    int ptr;
    char str[SIZE];
    FILE *fin;

    char getChar() {
        if (ptr == SIZE) {
            fread(str, 1, SIZE, fin);
            ptr = 0;
        }
        return str[ptr++];
    }

    int getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();

        int nr = 0, sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }

        while (isdigit(chr)) {
            nr = nr * 10 + chr - '0';
            chr = getChar();
        }
        return nr * sgn;
    }

  public:
    Parser(const char* str)
        : ptr(SIZE), fin(fopen(str, "r")) { }

    ~Parser() {
        fclose(fin);
    }

    friend Parser& operator>>(Parser& in, int& nr) {
        nr = in.getInt();
        return in;
    }
};

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

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;
}