Pagini recente » Cod sursa (job #1949795) | Cod sursa (job #1603715) | Cod sursa (job #2050685) | Cod sursa (job #1600801) | Cod sursa (job #2266601)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
struct el{
int indice, nr;
};
int n, k, curr;
deque <el> deq;
char s[3000100];
void read(int &x) {
x = 0;
int sign = 1;
if(s[curr] == '-') {
sign = -1;
curr ++;
}
while('0' <= s[curr] && s[curr] <= '9') {
x = x * 10 + (s[curr] - '0');
curr ++;
}
curr ++;
x *= sign;
}
int main() {
ios_base::sync_with_stdio(false);
in.getline(s, 3000100);
read(n);
read(k);
in.getline(s, 3000100);
curr = 0;
el x;
int valx;
read(valx);
x.nr = valx;
x.indice = 1;
deq.push_back(x);
for (int i = 2; i < k; i++) {
read(valx);
x.nr = valx;
x.indice = i;
while (!deq.empty() && x.nr < deq.back().nr)
deq.pop_back();
deq.push_back(x);
}
el maxi;
maxi.nr = -30005;
/* deq.pop_front();*/
for (int i = k; i <= n; i++) {
read(valx);
x.nr = valx;
x.indice = i;
while (!deq.empty() && x.nr < deq.back().nr) {
deq.pop_back();
}
deq.push_back(x);
if (deq.front().nr > maxi.nr) {
maxi.nr = deq.front().nr;
maxi.indice = i;
}
if (deq.back().indice - deq.front().indice == k - 1)
deq.pop_front();
}
out << maxi.indice - k + 1 << " " << maxi.indice << " " << maxi.nr;
return 0;
}