Pagini recente » Cod sursa (job #2698724) | Cod sursa (job #1950836) | Cod sursa (job #1017605) | Cod sursa (job #802541) | Cod sursa (job #1442497)
#include <fstream>
#include <cstdlib>
#include <vector>
#include <string>
using namespace std;
template <typename T>
class my_dq{
T* buf;
int st = 0, dr = -1;
public:
my_dq(const int maxsz){
buf = new T[maxsz]; }
~my_dq(){
delete[] buf; }
bool empty(){
return dr-st+1 == 0; }
T& front(){
return buf[st]; }
T& back(){
return buf[dr]; }
void push_back(const T& t){
buf[++dr] = t; }
void pop_back(){
--dr; }
void pop_front(){
++st; } };
void citeste_date(int& n, int& k, vector<int>& v){
ifstream f("secventa.in");
f >> n >> k;
v.resize(n);
for(auto& x : v){
f >> x; } }
template <typename T, typename cmp_t>
void push_deque(my_dq<T>& dq, T& t, cmp_t cmp){
while((!dq.empty()) && !cmp(dq.back(), t)){
dq.pop_back(); }
dq.push_back(t); }
int main(){
ifstream f("secventa.in");
ofstream g("secventa.out");
int n, k;
vector<int> v;
citeste_date(n, k, v);
my_dq<int> dq(k);
const auto cmp = [&v](const int a, const int b){
return v[a] < v[b]; };
for(int i = 0; i < k; ++i){
push_deque(dq, i, cmp); }
int rez = k-1, val = dq.front();
for(int i = k; i < n; ++i){
push_deque(dq, i, cmp);
if((!dq.empty()) && dq.front()+k == i){
dq.pop_front(); }
if((!dq.empty()) && cmp(val, dq.front())){
val = dq.front();
rez = i; } }
g << (rez-k+2) << ' ' << (rez+1) << ' ' << v[val] << '\n';
return 0; }