Pagini recente » Cod sursa (job #833348) | Cod sursa (job #124255) | Cod sursa (job #2793168) | Cod sursa (job #2578429) | Cod sursa (job #2786609)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
const int maxN = 500000;
int n, k, v[maxN + 5], ans = -0x3f3f3f3f, l, r;
string s;
deque <int> dq;
int main()
{
fin >> n >> k >> ws;
getline(fin, s);
int ind = 0;
for(int i = 1; i <= n; i++)
{
char c = s[ind];
int nr = 0, semn = 1;
if(c == ' ')
c = s[++ind];
if(c == '-')
{
semn = -1;
c = s[++ind];
}
while(ind < s.size() && s[ind] != ' ')
{
nr = nr * 10 + (c - '0');
c = s[++ind];
}
v[i] = semn * nr;
}
for(int i = 1; i <= k - 1; i++)
{
while(!dq.empty() && v[dq.back()] > v[i])
dq.pop_back();
dq.push_back(i);
}
for(int i = k; i <= n; i++)
{
while(!dq.empty() && v[dq.back()] > v[i])
dq.pop_back();
dq.push_back(i);
if(dq.front() == i-k)
dq.pop_front();
if(i >= k && v[dq.front()] > ans)
{
ans = v[dq.front()];
l = i - k + 1;
r = i;
}
}
fout << l << ' ' << r << ' ' << ans;
return 0;
}