Mai intai trebuie sa te autentifici.
Cod sursa(job #2482279)
Utilizator | 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;
}