Pagini recente » Cod sursa (job #2559267) | Cod sursa (job #710243) | Cod sursa (job #1939687) | Borderou de evaluare (job #2565362) | Cod sursa (job #1095467)
/*
* File: secventa.cpp
* Author: Vlad
*
* Created on January 31, 2014, 2:05 AM
*/
#include <cstdio>
#include <deque>
using namespace std;
const int MAX_N = 500001;
const int MIN_VAL = -10000000;
int n, k;
int a[MAX_N];
void slidingWindowMinimum() {
deque<int> q;
for (int i = 1; i <= k; i++) {
while (!q.empty() && a[q.back()] >= a[i]) {
q.pop_back();
}
q.push_back(i);
}
int maxVal = MIN_VAL, leftIdx = 1;
// minimum element in the window is the first in deque
for (int i = k + 1; i <= n; ++i) {
if (maxVal < a[q.front()]) {
maxVal = a[q.front()];
leftIdx = q.front();
}
while (!q.empty() && a[q.back()] >= a[i]) {
// pop elements that can't be minimum in the
// subsequent windows
q.pop_back();
}
while (!q.empty() && q.front() <= i - k) {
// pop elements that get out of the window
q.pop_front();
}
q.push_back(i);
}
if (maxVal < a[q.front()]) {
maxVal = a[q.front()];
leftIdx = q.front();
}
printf("%d %d %d\n", leftIdx, leftIdx + k - 1, maxVal);
}
int main(int argc, char** argv) {
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
slidingWindowMinimum();
return 0;
}