题目描述
点进去看吧,说的不能再清楚了。
Solution
看到数据规模不难想到二分 W,然后用个前缀和优化一下即可。注意上下界。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN=200010;
int n,m,s;
int maxx=-1,minn=0x3f3f3f3f;
int ans=(int)1e17l;
int Y,cnt;
int sumn[MAXN],sumv[MAXN];
int v[MAXN],w[MAXN];
int l[MAXN],r[MAXN];
int check(int x){
Y=cnt=0;
memset(sumn,0,sizeof(sumn));
memset(sumv,0,sizeof(sumv));
for(int i=1;i<=n;i++)
{
if(w[i]>=x) sumn[i]=sumn[i-1]+1,sumv[i]=sumv[i-1]+v[i];
else sumn[i]=sumn[i-1],sumv[i]=sumv[i-1];
}
for(int i=1;i<=m;i++)
Y+=(sumn[r[i]]-sumn[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
cnt=abs(Y-s);
return Y>s;
}
inline int read(){
int x=0; char c;
do c=getchar(); while(c<'0'||c>'9');
while(c>='0'&&c<='9')
x=x*10+c-48,c=getchar();
return x;
}
signed main(){
n=read();m=read();s=read();
for(int i=1;i<=n;++i){
w[i]=read();v[i]=read();
maxx=max(maxx,w[i]);minn=min(minn,w[i]);
}
for(int i=1;i<=m;++i){
l[i]=read();
r[i]=read();
}
int left=minn-1,right=maxx+2,mid;
while(left<=right){
mid=(left+right)/2;
if(check(mid))
left=mid+1;
else
right=mid-1;
ans=min(ans,cnt);
}
printf("%lld",ans);
}