Pagini recente » Cod sursa (job #2241976) | Cod sursa (job #2533815) | Cod sursa (job #1191596) | Cod sursa (job #2974728) | Cod sursa (job #1604200)
#include <iostream>
#include <deque>
using namespace std;
struct item {
int val;
int pos;
};
int main (void) {
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
char *in = (char *) malloc(1024 * 1024 * 10 * sizeof(char));
fgets(in, 1024 * 1024 * 10, stdin);
int n = 0, k = 0;
int idx;
for(; in[idx] >= '0' && in[idx] <= '9'; ++idx) {
n += n * 10 + in[idx] - '0';
}
while (in[idx] < '0' || in[idx] > '9') ++idx;
for(; in[idx] >= '0' && in[idx] <= '9'; ++idx) {
k += k * 10 + in[idx] - '0';
}
int v[500005] = {0};
fgets(in, 1024 * 1024 * 7, stdin);
idx = 0;
for (int i = 0; i < n; ++i) {
int sign = 1;
if (in[idx] == '-') {
sign = -1;
++idx;
}
while (in[idx] >= '0' && in[idx] <= '9') {
v[i] += v[i] * 10 + in[idx] - '0';
++idx;
}
v[i] *= sign;
while ((in[idx] < '0' || in[idx] > '9') && in[idx] != '-') ++idx;
}
deque<item> l;
item aux;
int max = l.front().val, startSol = l.front().pos;
for (int i = 0; i < k; ++i) {
while (!l.empty() && v[i] <= l.back().val) {
l.pop_back();
}
aux.val = v[i];
aux.pos = i;
l.push_back(aux);
}
max = l.front().val;
startSol = l.front().pos;
for (int i = k; i < n; ++i) {
while (!l.empty() && v[i] <= l.back().val) {
l.pop_back();
}
aux.val = v[i];
aux.pos = i;
l.push_back(aux);
if (l.front().pos <= i - k) l.pop_front();
if (l.front().val > max) {
max = l.front().val;
startSol = i;
}
}
while (startSol && v[startSol] >= max) --startSol;
if (v[startSol] < max) ++startSol;
cout << startSol + 1 << " " << startSol + k << " " << max;
free(in);
return 0;
}