Pagini recente » Cod sursa (job #1624235) | Cod sursa (job #1528758) | Cod sursa (job #310520) | Cod sursa (job #1514795) | Cod sursa (job #1838314)
#include <fstream>
using namespace std;
int n,x,y,z,i,j,l,st,dr,m,mini,k,a[100005],rmq1[20][100005],rmq2[20][100005];
int cost(int lu)
{
l=a[lu];
mini=max(rmq1[l][1], rmq1[l][lu-(1<<l)+1])-min(rmq2[l][1], rmq2[l][lu-(1<<l)+1]);
for(i=2; i<=n-lu+1; i++)
{
k=max(rmq1[l][i], rmq1[l][i+lu-(1<<l)])-min(rmq2[l][i], rmq2[l][lu-(1<<l)+i]);
if(k<mini) mini=k;
}
return mini;
}
int poz(int lu)
{
int p;
l=a[lu];
mini=max(rmq1[l][1],rmq1[l][lu-(1<<l)+1])-min(rmq2[l][1], rmq2[l][lu-(1<<l)+1]);
p=1;
for(i=2; i<=n-lu+1; i++)
{
k=max(rmq1[l][i],rmq1[l][i+lu-(1<<l)])-min(rmq2[l][i], rmq2[l][lu-(1<<l)+i]);
if(k<mini)
{
mini=k;
p=i;
}
else if(k==mini/*&&rmq1[0][p]<=rmq1[0][i]*/) p=i;
}
return p;
}
int main()
{
ifstream f("sir.in");
ofstream g("sir.out");
f>>n>>x>>y>>z;
for(i=1; i<=n; i++)
{
f>>rmq1[0][i];
rmq2[0][i]=rmq1[0][i];
}
for(i=2; i<100000; i*=2)
a[i]=1;
for(i=1; i<=100000; i++)
a[i]+=a[i-1];
for(i=1; 1<<i <=n; i++)
{
l=1<<(i-1);
for(j=1; j<=n-2*l+1; j++)
{
rmq1[i][j]=max(rmq1[i-1][j],rmq1[i-1][j+l]);
rmq2[i][j]=min(rmq2[i-1][j],rmq2[i-1][j+l]);
}
}
if(cost(x)>z) g<<"-1\n";
else if(cost(y)<z) g<<"-1\n";
else
{
st=x;
dr=y;
while(st+1<dr)
{
m=(st+dr)/2;
if(cost(m)<=z) st=m;
else dr=m;
}
if(cost(dr)>z) dr=st;
g<<dr<<" "<<poz(dr)<<" "<<poz(dr)+dr-1<<'\n';
}
f.close(); g.close();
return 0;
}