Pagini recente » Cod sursa (job #2267890) | Cod sursa (job #1491880) | Cod sursa (job #307537) | Cod sursa (job #1759525) | Cod sursa (job #3258450)
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
ifstream cin("secventa.in");
ofstream cout("secventa.out");
deque<int> window;
int n, k, nr;
int pos, val;
vector<int> nums;
int main() {
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> nr;
nums.push_back(nr);
}
// initial deque - first window
for (int i = 0; i < k; ++i) {
while (!window.empty() && nums[i] < nums[window.back()])
window.pop_back();
window.push_back(i);
}
// the maximum value of the first window
// is the front element of the deque
pos = 0;
val = nums[window.front()];
if (window.front() == 0) // first element of array
window.pop_front();
for (int i = k; i < n; ++i) {
while (!window.empty() && nums[i] < nums[window.back()])
window.pop_back();
window.push_back(i);
if (nums[window.front()] > val) {
val = nums[window.front()];
pos = i - k + 1;
}
if (window.front() == i - k + 1)
window.pop_front();
}
int lim = pos + k;
while (pos - 1 >= 0 && nums[pos - 1] > val)
pos --;
cout << pos + 1 << ' ' << lim << val;
cin.close();
cout.close();
return 0;
}