Pagini recente » Cod sursa (job #46534) | Cod sursa (job #821287) | Cod sursa (job #468830) | Cod sursa (job #676275) | Cod sursa (job #16454)
Cod sursa(job #16454)
/*
problema secventa infoarena.ro
implementare: deque
testat:
RMQ: 70 pct
heap_cu_set: 40 pct
heap_cu_priority_queue: 80 pct
*/
#include <cstdio>
#include <deque>
using namespace std;
int N, K, i, j;
struct nod{
int val, id;
nod(int _v, int _i) {val = _v; id = _i;};
nod(){};
};
deque<nod> Q;
int main() {
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
scanf("%d %d", &N, &K);
int sol = -32222, left;
for (i=1; i<=N; i++) {
int X;
scanf("%d", &X);
//X se duce la dreapta
//scot din dreapta tot ce este mai mare ca X
while (!Q.empty()) {
nod A = Q.back();
if (A.val > X) Q.pop_back();
else break;
}
Q.push_back(nod(X, i));
//baga in dreapta X
//scoate din stanga tot ce este mai batran de K pasi
while (!Q.empty()) {
nod A = Q.front();
if (A.id < i - K + 1) Q.pop_front();
else break;
}
nod A = Q.front();
if (A.val > sol) {left = i - K +1; sol = A.val;}
}
printf("%d %d %d\n", left, left+K-1, sol);
return 0;
}