又菜又爱玩 @ 2021-12-26 10:57:06
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define N 200005
using namespace std;
long long w[N],v[N],l[N],r[N],qn[N],qv[N],sum;
long long n,m,s,W=0,maxx;
bool check(long long mid)
{
int y=0;
for(int i=1;i<=N-1;i++)
{
qn[i]=0;
qv[i]=0;
}
for(int i=1;i<=n;i++)
{
if(w[i]>=mid)
{
qn[i]=qn[i-1]+1;
qv[i]=qv[i-1]+v[i];
}
else
{
qn[i]=qn[i-1];
qv[i]=qv[i-1];
}
}
for(int i=1;i<=m;i++)
{
y=y+(qn[r[i]]-qn[l[i]-1])*(qv[r[i]]-qv[l[i]-1]);
}
sum=abs(y-s);
if(y>s)
return 1;
return 0;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&w[i],&v[i]);
maxx=max(maxx,w[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&l[i],&r[i]);
}
long long ans=2e18;
long long low=0;
long long high=maxx+2;
while(low<=high)
{
long long mid=(low+high)/2;
if(check(mid))
{
low=mid+1;
W=mid;
}
else
{
high=mid-1;
}
ans=min(sum,ans);
}
printf("%lld",ans);
return 0;
}