Pagini recente » Cod sursa (job #3037899) | Cod sursa (job #129232) | Cod sursa (job #188093) | Statistici Stefan Grecu (StefanGrecu) | Cod sursa (job #2482271)
#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;
}