Pagini recente » Cod sursa (job #1525137) | Cod sursa (job #908486) | Cod sursa (job #1627588) | Cod sursa (job #2415062) | Cod sursa (job #1862676)
#include <cstdio>
#include <deque>
using namespace std;
struct nod{
int val, id;
nod(int _v, int _i) {val = _v; id = _i;};
nod(){};
};
int main() {
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
int N, K, i, j;
deque<nod> Q;
scanf("%d %d\n", &N, &K);
char c[7];
int sol = -32222, left;
for (i=1; i<K; i++) {
int X = 0;
int neg = 1;
scanf("%s", &c);
int dd = 0;
if (c[0] == '-') neg =-1, dd = 1;
for (; c[dd]; dd++) {
X*=10; X+=c[dd]-'0';
}
X*=neg;
//printf("AM: %d\n", X);
//X se duce la dreapta
//scot din dreapta tot ce este mai mare ca X
while (!Q.empty()) {
nod A = Q.front();
if (A.val >= X) Q.pop_front();
else break;
}
Q.push_front(nod(X, i));
//baga in dreapta X
//scoate din stanga tot ce este mai batran de K pasi
while (!Q.empty()) {
nod A = Q.back();
if (A.id < i - K + 1) Q.pop_back();
else break;
}
}
for (i=K; i<=N; i++) {
int X = 0;
int neg = 1;
scanf("%s", &c);
int dd = 0;
if (c[0] == '-') neg =-1, dd = 1;
for (; c[dd]; dd++) {
X*=10; X+=c[dd]-'0';
}
X*=neg;
//printf("AM: %d\n", X);
//X se duce la dreapta
//scot din dreapta tot ce este mai mare ca X
while (!Q.empty()) {
nod A = Q.front();
if (A.val >= X) Q.pop_front();
else break;
}
Q.push_front(nod(X, i));
//baga in dreapta X
//scoate din stanga tot ce este mai batran de K pasi
while (!Q.empty()) {
nod A = Q.back();
if (A.id < i - K + 1) Q.pop_back();
else break;
}
nod A = Q.back();
if (A.val > sol) {left = i - K +1; sol = A.val;}
}
printf("%d %d %d\n", left, left+K-1, sol);
return 0;
}