Milk_Feng @ 2019-04-30 20:22:49
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define Reg register
using namespace std;
int lef[100050],rig[100050],num[100050];
long long n,m,s,ans,tot=0x7ffffffffff,maxx;
long long wos[100050],val[100050],sum[100050];
inline long long max(long long x,long long y) {return x>y?x:y;}
inline long long min(long long x,long long y) {return x<y?x:y;}
inline long long abc(long long x) {return x>=0?x:(-x);}
inline long long js(int x)
{
long long ans=0;
memset(sum,0,sizeof(sum));
memset(num,0,sizeof(num));
for(Reg int i=1;i<=n;i++)
{
sum[i]=sum[i-1]; num[i]=num[i-1];
if(wos[i]>=x) sum[i]+=val[i],num[i]++;
}
for(Reg int i=1;i<=m;i++)
{
int l=lef[i],r=rig[i];
ans+=(long long)(num[r]-num[l-1])*(sum[r]-sum[l-1]);
}
return ans;
}
inline bool judge(int x)
{
long long ans=js(x);
tot=min(tot,abc(ans-s));
if(ans>s) return 1;
else if(ans<s) return 0;
else return 2;
}
inline int erfen(long long l,long long r)
{
if(l==r) return l;
long long mid=(l+r)>>1;
int jud=judge(mid);
if(jud==0) return erfen(l,mid);
else if(jud==1) return erfen(mid+1,r);
else return mid;
}
int main()
{
cin>>n>>m>>s;
for(Reg int i=1;i<=n;i++)
{
scanf("%lld%lld",&wos[i],&val[i]);
maxx=max(maxx,wos[i]);
}
for(Reg int i=1;i<=m;i++) scanf("%d%d",&lef[i],&rig[i]);
int ans=erfen(1,maxx); tot=min(tot,abc(s-js(ans)));
cout<<tot;
return 0;
}
85分代码, 求dalao帮忙。。