Pagini recente » Cod sursa (job #188388) | Cod sursa (job #364497) | Cod sursa (job #2825168) | Cod sursa (job #64275) | Cod sursa (job #2474362)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
const int MAXN = 5 * 1e5, MAXVAL = 3 * 1e4;
int arr[MAXN], n, k;
struct minCmp {
bool operator() (int a, int b) const {
return a < b;
}
};
template <class Compare>
class Deque {
private:
int cont[MAXN], left, right;
Compare cmp;
public:
Deque() {
left = 0;
right = 0;
}
int getMin(int value) {
while (value - cont[left] >= k && left < right)
++left;
return this->cont[left];
}
void pushBack(int value) {
cont[right++] = value;
}
void popBack(int value) {
while (cmp(arr[value], arr[cont[right - 1]]) && right > left)
--right;
}
};
void read() {
fin >> n >> k;
for (int i = 0; i < n; ++i)
fin >> arr[i];
}
void solve() {
Deque<minCmp> deque;
int max = -(MAXVAL + 1), ind1, ind2;
for (int i = 0; i < k - 1; ++i) {
deque.popBack(i);
deque.pushBack(i);
}
for (int i = k - 1; i < n; ++i) {
int min;
deque.popBack(i);
deque.pushBack(i);
min = deque.getMin(i);
if (arr[min] > max) {
max = arr[min];
ind1 = i - k + 1;
ind2 = i;
}
}
fout << ind1 + 1 << ' ' << ind2 + 1 << ' ' << max << '\n';
}
int main() {
read();
solve();
return 0;
}