Pagini recente » Cod sursa (job #475828) | Cod sursa (job #2837542) | Cod sursa (job #858765) | Cod sursa (job #725468) | Cod sursa (job #2251545)
#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > vll;
typedef vector< pii > vpii;
typedef vector< pll > vpll;
typedef long double ld;
const ll MOD = 1e9 + 7;
ll lgput(ll a, ll b, ll mod) {
ll ret = 1;
while( b ){
if(b & 1) ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret;
}
int binarySearch(vector< int > &v, int value) {
int best = 0;
for(int step = 29; step >= 0; --step) {
if(best + (1<<step) < v.size() && v[best + (1<<step)] <= value) best += (1<<step);
}
return best;
}
inline ll inv(ll x, ll MOD) {
return lgput(x, MOD - 2, MOD);
}
deque< pair< int, int > > dq;
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
int main() {
//freopen("input", "r", stdin); freopen("output", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
cout << fixed;
InParser f("secventa.in");
freopen("secventa.out", "w", stdout);
int l, r, ans = -1e9;
int n, k;
f >> n >> k;
for(int i = 1; i <= n; ++i) {
int x;
f >> x;
while(dq.size() && dq.front().first <= i-k) dq.pop_front();
while(dq.size() && dq.back().second > x) dq.pop_back();
dq.push_back(make_pair(i, x));
if(i < k) continue;
if(dq.front().second > ans) {
ans = dq.front().second;
r = i;
l = i - k + 1;
}
}
printf("%d %d %d\n", l, r, ans);
return 0;
}