Pagini recente » Cod sursa (job #600415) | Cod sursa (job #429770) | Cod sursa (job #2426217) | Cod sursa (job #2744676) | Cod sursa (job #211222)
Cod sursa(job #211222)
// http://infoarena.ro/problema/secventa
#include <cstdio>
#include <climits>
/*#include <deque>
using namespace std;
deque<int> Min;*/
int Min[500001];
int n, k, A[500001];
int ans, ansPos;
#define DONE
int main() {
freopen("secventa.in", "r", stdin);
#ifdef DONE
freopen("secventa.out", "w", stdout);
#endif
scanf("%d %d", &n, &k);
int i;
for (i = 0; i < n; ++ i)
scanf("%d", &A[i]);
ans = INT_MIN, ansPos = -1;
//deque<int>::iterator di;
int ds = 0, de = -1;
for (i = 0; i < n; ++ i) {
if (de >= ds && i >= Min[ds] + k)
++ ds;
if (de < ds || A[i] > A[Min[de]]) {
Min[++ de] = i;
} else {
while (de >= ds && A[i] < A[Min[de]])
-- de;
Min[++ de] = i;
}
/*for (int j = ds; j <= de; ++ j)
printf("%d ", A[Min[j]]);
printf("\n");*/
if (i >= k - 1 && ans < A[Min[ds]]) {
ans = A[Min[ds]];
ansPos = i;
}
}
printf("%d %d %d\n", ansPos - k + 2, ansPos + 1, ans);
return 0;
}