Pagini recente » Cod sursa (job #1391758) | Cod sursa (job #2818289) | Cod sursa (job #2929904) | Cod sursa (job #2132377) | Cod sursa (job #2163855)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int i,x,y,v[500002],semn,j,p,u,maxi,n,m;
deque <int> q;
char s[5*500002];
int main()
{
fin>>n>>m;
fin.get();
fin.get(s,500002);
j=0;
for(i=1; i<=n; i++) {
semn=1;
if(s[j]=='-') {
semn=-1;
j++;
}
while(s[j]>='0' && s[j]<='9') {
v[i]=v[i]*10+s[j]-'0';
j++;
}
v[i]*=semn;
j++;
}
/*for(i=1;i<=n;++i)
{
while(!q.empty() && v[q.back()]>v[i])
{
q.pop_back();
}
q.push_back(i);
while(q.front()==i-m)
{
q.pop_front();
}
if(maxi<v[q.front()] && i>=m)
{
maxi=v[q.front()];
u=i;
p=i-m+1;
}
}
fout<<p<<" "<<u<<" "<<maxi<<'\n';*/
for(i=1; i<=m; i++)
{
while(q.size()>=1&&v[q.front()]>=v[i])
{
q.pop_front();
}
q.push_front(i);
}
if(v[q.back()]>maxi)
{
maxi=v[q.back()];
u=m;
p=1;
}
for(i=m+1; i<=n; i++)
{
while(q.size()>=1&&q.back()<=i-m)q.pop_back();
while(q.size()>=1&&v[q.front()]>=v[i])
{
q.pop_front();
}
q.push_front(i);
if(v[q.back()]>maxi)
{
maxi=v[q.back()];
u=i;
p=i-m+1;
}
}
fout<<p<<" "<<u<<" "<<maxi;
return 0;
}