Pagini recente » Cod sursa (job #1035991) | Cod sursa (job #1937394) | Cod sursa (job #2779048) | Cod sursa (job #734139) | Cod sursa (job #1728350)
#include <fstream>
#define NMAX 500005
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
int n , k , st , dr , sol , p;
int v[NMAX] , dq[NMAX];
int main() {
f >> n >> k;
for (int i = 1; i <= n; ++i) {
f >> v[i];
}
st = dr = 1;
dq[1] = 1;
for (int i = 2; i <= k; ++i) {
int j = dr + 1;
while (j > 0 && v[i] <= v[dq[j]]) {
--j;
}
dr = j + 1;
dq[dr] = i;
}
sol = dq[st];
p = 1;
for (int i = k + 1; i <= n; ++i) {
if (dq[st] < i - k + 1) {
++st;
}
int j = dr;
while (j >= st && v[i] <= v[dq[j]]) {
--j;
}
dr = j + 1;
dq[dr] = i;
if (v[dq[st]] > sol) {
sol = v[dq[st]];
p = i - k + 1;
}
}
g << p << " " << p + k - 1 << " " << sol;
return 0;
}