Pagini recente » Cod sursa (job #508829) | Cod sursa (job #1063685) | Cod sursa (job #2536557) | Cod sursa (job #1687395) | Cod sursa (job #2722934)
#include <fstream>
#include <deque>
#include <vector>
using namespace std;
int n, k;
int a[500001];
int Max, st, dr;
class InParser {
private:
vector<char> str;
int ptr;
ifstream fin;
char getChar() {
if (ptr == (int) str.size()) {
fin.read(str.data(), str.size());
ptr = 0;
}
return str[ptr++];
}
template<class T>
T getInt() {
char chr = getChar();
while (!isdigit(chr) && chr != '-')
chr = getChar();
int sgn = +1;
if (chr == '-') {
sgn = -1;
chr = getChar();
}
T num = 0;
while (isdigit(chr)) {
num = num * 10 + chr - '0';
chr = getChar();
}
return sgn * num;
}
public:
InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
~InParser() { fin.close(); }
template<class T>
friend InParser& operator>>(InParser& in, T& num) {
num = in.getInt<T>();
return in;
}
};
void read() {
int i;
InParser f("secventa.in");;
f >> n >> k;
for (i = 1; i <= n; i++)
f >> a[i];
}
deque<int> dq;
void solve() {
int i;
Max = -500005;
st = 0, dr = 0;
for (i = 1; i <= n; i++) {
while (dq.size() > 0 && a[i] <= a[dq.back()])
dq.pop_back();
dq.push_back(i);
while (dq.size() > 0 && dq.front() + k <= i)
dq.pop_front();
if (i >= k)
if (a[dq.front()] > Max) {
Max = a[dq.front()];
st = i - k + 1, dr = i;
}
}
}
void output() {
ofstream g("secventa.out"); g.tie(0);
g << st << ' ' << dr << ' ' << Max;
g.close();
}
int main() {
ios::sync_with_stdio(0);
read();
solve();
output();
return 0;
}