Pagini recente » Cod sursa (job #1517639) | Cod sursa (job #3183471) | Cod sursa (job #1388283) | Cod sursa (job #1993644) | Cod sursa (job #211219)
Cod sursa(job #211219)
// 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 = 0;
for (i = 0; i < n; ++ i) {
if (de - ds > 0 && i >= Min[ds] + k)
++ ds;
if (de - ds == 0 || A[i] > A[Min[de]]) {
Min[++ de] = i;
} else {
while (de - ds > 0 && A[i] < A[Min[de]])
-- de;
Min[++ de] = i;
}
/*for (di = Min.begin(); di != Min.end(); ++ di)
printf("%d ", A[*di]);
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;
}