Gadfly @ 2018-08-03 21:15:20
#include<iostream>
#include<cstring>
#include<algorithm>
#define R register
#define F(i,a,b) for(R int i=a;i<=b;i++)
#define M 200010
using namespace std;
typedef long long ll;
int w[M],v[M],LL[M],rr[M];
int n,m;
ll s,SUM,ans=0x7fffffff;
ll qs[M],qc[M];
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
bool check(int k)
{
SUM=0;
//F(i,0,n+1){q[i].c=0; q[i].sum=0;}
memset(qc,0,sizeof(qc));
memset(qs,0,sizeof(qs));
F(i,1,n)
{
if(w[i]>=k) {qc[i]=qc[i-1]+1; qs[i]=qs[i-1]+v[i];}
else {qc[i]=qc[i-1]; qs[i]=qs[i-1];}
}
F(i,1,m)
{
SUM+=(qc[rr[i]]-qc[LL[i]-1])*(qs[rr[i]]-qs[LL[i]-1]);//∑
}
return SUM>=s;
}
int main()
{
int l=0x7fffffff,r=-1;
//ios::sync_with_stdio(false);
scanf("%d%d%lld",&n,&m,&s);
//cout<<n<<" "<<m<<" "<<s<<endl;
F(i,1,n) {scanf("%d%d",&w[i],&v[i]); r=max(r,w[i]); l=min(l,w[i]);}
F(i,1,m) scanf("%d%d",&LL[i],&rr[i]);
l--; r++;//判断全部都选和全部都不选的情况
//cout<<l<<" "<<r<<endl;
int mid=(l+r)>>1;
while(l<=r)
{
if(check(mid)) l=mid+1;
else r=mid-1;
mid=(l+r)>>1;
ans=min(ans,llabs(SUM-s));
}
printf("%lld",ans);
return 0;
}
by edjzy @ 2018-08-04 00:17:31
@龘靐齉齾麤 what