star_magic_young @ 2018-03-04 19:38:00
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
long long n,m,s;
long long ans;
long long v[200010][2],l=0,r,mid,q[200010][2];
long long x[200010],ss[200010];
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
ans=s<<10;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&v[i][0],&v[i][1]);
r=max(r,v[i][0]);
}
long long rr=r;
for(int i=1;i<=m;i++)
scanf("%lld%lld",&q[i][0],&q[i][1]);
while(l<r-1)
{
mid=(l+r)/2;
//cout<<mid<<endl;
for(int i=1;i<=n;i++)
{
if(v[i][0]>=mid)
{
x[i]=x[i-1]+1;
ss[i]=ss[i-1]+v[i][1];
}
else
{
x[i]=x[i-1];
ss[i]=ss[i-1];
}
}
/*for(int i=1;i<=n;i++) cout<<x[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++) cout<<ss[i]<<" ";
cout<<endl;*/
long long xs=0;
for(int i=1;i<=m;i++)
xs+=(x[q[i][1]]-x[q[i][0]-1])*(ss[q[i][1]]-ss[q[i][0]-1]);
//cout<<xs<<endl;
ans=min(ans,abs(s-xs));
if(s-xs<1LL*0) l=mid;
else r=mid;
}
l=max(1LL*0,l-2);r=min(rr,r-2);
for(;l<=r;l++)
{
for(int i=1;i<=n;i++)
{
if(v[i][0]>=l)
{
x[i]=x[i-1]+1;
ss[i]=ss[i-1]+v[i][1];
}
else
{
x[i]=x[i-1];
ss[i]=ss[i-1];
}
}
long long xs=0;
for(int i=1;i<=m;i++)
xs+=(x[q[i][1]]-x[q[i][0]-1])*(ss[q[i][1]]-ss[q[i][0]-1]);
ans=min(ans,abs(s-xs));
}
printf("%lld",ans);
return 0;
}
by 李不似 @ 2020-10-12 20:02:35
十三过不去加一