Pagini recente » Cod sursa (job #2263275) | Cod sursa (job #963375) | Cod sursa (job #2797331) | Cod sursa (job #703579) | Cod sursa (job #2473815)
#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() const{
return this->cont[left];
}
void pushBack(int value) {
cont[right++] = value;
}
void popFront(int value) {
while (value - cont[left] >= k && left < right)
++left;
}
void popBack(int value) {
while (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), ind;
deque.pushBack(0);
deque.popBack(1);
deque.pushBack(1);
for (int i = 2; i < n; ++i) {
int min;
deque.popBack(i);
deque.popFront(i);
deque.pushBack(i);
min = deque.getMin();
if (arr[min] > max) {
max = arr[min];
ind = min;
}
}
fout << ind + 1 << ' ' << ind + k << ' ' << max << '\n';
}
int main() {
read();
solve();
return 0;
}