Pagini recente » Cod sursa (job #2256630) | Cod sursa (job #2126804)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int v[500005],i,dp[500005],semn;
char s[3500001];
int main()
{
int n,k;
fin>>n>>k;
fin.get();
fin.get(s,3500001);
int lun=strlen(s);
int p=1;
for(i=0;i<=lun;++i)
{
semn=1;
if(s[i]=='-')
{
semn=0;
i++;
}
while(s[i]>='0'&&s[i]<='9')
{
v[p]=v[p]*10+s[i]-'0';
i++;
}
if(semn==0)
v[p]=-v[p];
p++;
}
int st=1;
int dr=0;
int pozi;
int minm=-1000000000;
for(int i=1;i<=n;i++)
{
while(v[i]<v[dp[dr]]&&st<=dr)
dr--;
dr++;
dp[dr]=i;
if(i-dp[st]==k)
st++;
if(i>=k)
if(minm<v[dp[st]])
{
pozi=i-k+1;
minm=v[dp[st]];
}
}
fout<<pozi<<' '<<pozi+k-1<<' '<<minm;
return 0;
}
/*#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream si("secventa.in");
ofstream so("secventa.out");
int v[500005];
int dp[500005];
char s[3500001];
int main()
{
int n,k;
si>>n>>k;
si.get();
si.get(s,3500001);
int l=strlen(s),p=1;
for(int i=0;i<=l;++i)
{
int semn=1;
if(s[i]=='-')
{
semn=0;
i++;
}
while(s[i]>='0'&&s[i]<='9')
{
v[p]=v[p]*10+s[i]-'0';
i++;
}
if(semn==0)
v[p]=-v[p];
p++;
}
int st=1,fi=0;
int pozi,minm=-1000000000;
for(int i=1;i<=n;i++)
{
while(v[i]<v[dp[fi]]&&st<=fi)
fi--;
fi++;
dp[fi]=i;
if(i-dp[st]==k)
st++;
if(i>=k)
if(minm<v[dp[st]])
{
pozi=i-k+1;
minm=v[dp[st]];
}
}
so<<pozi<<' '<<pozi+k-1<<' '<<minm;
return 0;
}
*/