无情。浪剑心 @ 2020-10-23 16:59:48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,s;
ll rid,mid;
ll lef=0x3f3f3f3f3f3f3f3f;
ll cnt;
ll w[200005],v[200005];
ll a[200005],b[200005];
ll now,cmp;
ll sum[200005];
ll g[200005];
ll minn=0x3f3f3f3f3f3f3f3f;
bool check(int x)
{
now=0; cmp=0;
memset(sum,0,sizeof(sum)); memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
if(w[i]>=x)
{
sum[i]=v[i]+sum[i-1]; g[i]=g[i-1]+1;
}
else
{
sum[i]=sum[i-1]; g[i]=g[i-1];
}
}
for(int i=1;i<=m;i++)
{
cmp+=(sum[b[i]]-sum[a[i]-1])*(g[b[i]]-g[a[i]-1]);
}
now=llabs(cmp-s);
if(cmp>s) return true;
else return false;
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
rid=max(rid,w[i]);
lef=min(lef,w[i]);
}
for(int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
}
lef--;rid+=2;
while(lef<=rid)
{
mid=(lef+rid)/2;
if(check(mid)==true) lef=mid+1;
else rid=mid-1;
if(minn>now) minn=now;
}
printf("%lld",now);
return 0;
}