Pagini recente » Cod sursa (job #373759) | Cod sursa (job #1436080) | Cod sursa (job #657842) | Cod sursa (job #2099531) | Cod sursa (job #3032037)
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("secventa.in");
ofstream cout("secventa.out");
const int N = 5 * 1e5 + 9, Inf = 0x3f3f3f3f;
int n,k,v[N];
int ans = -Inf,poz = -1;
class dqueue
{
private:
deque<pair<int,int>> dq;
public:
void push(int val,int ind)
{
while(!dq.empty() && dq.back().first >= val)
dq.pop_back();
dq.push_back({val,ind});
}
int query(int ind)
{
while(!dq.empty() && dq.front().second < ind)
dq.pop_front();
if(dq.size() == 0)return -1;
return dq.front().first;
}
};
int main()
{
cin>>n>>k;
for(int i = 1; i <= n; ++i)
cin>>v[i];
dqueue dq;
for(int i = 1; i < k; ++i)
dq.push(v[i],i);
for(int i = k; i <= n; ++i)
{
dq.push(v[i],i);
int mn = dq.query(i-k+1);
if(ans < mn)
{
ans = mn;
poz = i;
}
}
cout<<poz-k+1<<' '<<poz<<' '<<ans;
return 0;
}