C202216chenyuxiao @ 2020-02-27 15:56:54
#include<cstdio>
#include<cmath>
#define MAXN 2000005
const long long INF=1e20;
long long n,m,s,w[MAXN],v[MAXN],l[MAXN],r[MAXN],sumv[MAXN],sumn[MAXN];
long long maxx,minn=INF,ans=INF;
long long Y(long long m1) {
long long ans1=0;
for(long long i=1;i<=n;i++)
{
if(w[i]>=m1)
{
sumv[i]=sumv[i-1]+v[i];
sumn[i]=sumn[i-1]+1;
}
else
{
sumv[i]=sumv[i-1];
sumn[i]=sumn[i-1];
}
}
for(int i=1;i<=m;i++)
{
ans1+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
}
return ans1;
}
int main()
{
scanf("%lld %lld %lld", &n, &m, &s);
for(long long i=1;i<=n;i++)
{
scanf("%lld %lld", &w[i], &v[i]);
if(w[i]>maxx)
{
maxx=w[i];
}
if(w[i]<minn)
{
minn=w[i];
}
}
for(long long i=1;i<=m;i++)
{
scanf("%lld %lld", &l[i], &r[i]);
}
long long l=minn-1,r=maxx+2;
while(l<=r)
{
long long mid=(l+r)/2,t=Y(mid),low=abs(s-t);
if(t>s)
{
l=mid+1;
}
else
{
r=mid-1;
}
if(low<ans)
{
ans=low;
}
}
printf("%lld", ans);
return 0;
}
为什么只有45分其他的全部WA