Pagini recente » Cod sursa (job #2200087) | Cod sursa (job #2786695) | Cod sursa (job #42503) | Cod sursa (job #2285839) | Cod sursa (job #1455376)
#include <iostream>
#include <fstream>
#include <assert.h>
#include <list>
#define mkpair(a,b) std::make_pair((a),(b))
#define tuple std::pair<int,int>
const char IN[] = "secventa.in", OUT[] = "secventa.out";
const int NMAX = 500000;
const int INF = 0x3f3f3f3f;
using namespace std;
int K, N;
int V[NMAX];
int best[NMAX];
int st[NMAX];
inline void read_data() {
assert(freopen(IN, "r", stdin));
assert(scanf("%d %d", &N, &K));
for (int i = 0; i < N; ++i)
assert(scanf("%d", &V[i]));
fclose(stdout);
}
inline void PD() {
int best = -INF, best_start = -1, best_end = -1;
list<tuple> deq;
for (int i = 0; i < N; ++i) {
while (!deq.empty() && deq.back().first >= V[i]) {
deq.pop_back();
}
while (!deq.empty() && i - deq.front().second >= K) {
deq.pop_front();
}
deq.push_back(mkpair(V[i], i));
if (i >= K - 1) {
if (deq.front().first > best) {
best = deq.front().first;
best_start = i - K + 1;
best_end = i;
}
}
}
fprintf(fopen(OUT, "w"), "%d %d %d\n", best_start + 1, best_end + 1, best);
}
int main() {
read_data();
PD();
return 0;
}