Pagini recente » Cod sursa (job #1750403) | Cod sursa (job #171591) | Cod sursa (job #155089) | Cod sursa (job #1701543) | Cod sursa (job #1387589)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
template<typename T>
class Deque {
public:
Deque(unsigned max_length) :
cont(max_length),
size(0),
back_ind(0),
front_ind(0) {}
void pop_back() {
size--;
back_ind--;
}
void pop_front() {
size--;
front_ind++;
}
bool empty() {
return size == 0;
}
void push_back(const T &val) {
size++;
cont[++back_ind] = val;
}
const T& front() {
return cont[front_ind];
}
const T& back() {
return cont[back_ind];
}
private:
vector<T> cont;
size_t size;
size_t back_ind;
size_t front_ind;
};
int main() {
ifstream in("secventa.in");
int n,k;
in >> n >> k;
vector<int> values(n+1);
for(int i = 1; i <= n; ++i) {
in >> values[i];
}
int max_value = -32012;
int max_ind = -1;
Deque<int> dq(n+20);
for(int i = 1; i <= n; ++i) {
while(!dq.empty() && values[dq.back()] > values[i])
dq.pop_back();
dq.push_back(i);
while(dq.front() <= i-k) {
dq.pop_front();
}
if(i >= k && values[dq.front()] > max_value) {
max_value = values[dq.front()];
max_ind = i;
}
}
ofstream out("secventa.out");
out << max_ind-k+1 << ' ' << max_ind << ' ' << max_value << '\n';
return 0;
}