Pagini recente » Cod sursa (job #924869) | Cod sursa (job #326820) | Cod sursa (job #1534367) | Diferente pentru problema/cuba intre reviziile 3 si 2 | Cod sursa (job #1603732)
#include <fstream>
#include <vector>
#include <deque>
#include <cstring>
#include <string>
#define INF 30001
using namespace std;
ifstream cin ("secventa.in");
ofstream cout ("secventa.out");
deque <int> dq;
string str;
int seq[500005], total_lng, k, total_max = -30001, max_val_l, max_val_r, sign, nr, seq_count = 1;
/*inline bool dq_empty() {
return l == r;
}
inline void dq_pop_back() {
--r;
}
inline void dq_pop_front() {
++l;
}
inline void dq_push_back(int n) {
++r;
dq[r] = n;
}
inline void dq_push(int n) {
while(l <= r and seq[n] < seq[r]) {
--r;
}
++r;
dq[r] = n;
}*/
inline void dq_push(int n) {
while(!dq.empty() and seq[n] < seq[dq.back() ]) {
dq.pop_back();
}
dq.push_back(n);
}
void read() {
char ch;
cin >> total_lng >> k >> ch;
getline(cin, str);
sign = 1;
seq[0] = -INF;
if(ch == '-') {
sign = -1;
}
if(isdigit(ch) ) {
nr *= 10;
nr += ch - '0';
}
//cout << str << '\n';
for(int i = 0; i < (int)str.size(); ++i) {
if(str[i] == ' ') {
seq[seq_count] = nr * sign;
++seq_count;
sign = 1;
nr = 0;
continue;
}
if(str[i] == '-') {
sign = -1;
}
if(isdigit(str[i]) ) {
nr *= 10;
nr += str[i] - '0';
}
}
seq[seq_count] = nr * sign;
}
void solve() {
for(int i = 1; i <= k - 1; ++i) {
dq_push(i);
}
for(int i = k; i <= total_lng; ++i) {
dq_push(i);
if(dq.front() == i - k) {
dq.pop_front();
}
if(seq[dq.front() ] > total_max) {
total_max = seq[dq.front() ];
max_val_l = i - k + 1;
max_val_r = i;
}
}
}
void print() {
cout << max_val_l << ' ' << max_val_r << ' ' << total_max << '\n';
}
int main() {
read();
solve();
print();
return 0;
}