$Sol$
首先$W$一定是某个$w_i$.于是一种暴力方法就出炉了,枚举$W$再计算.
注意到,满足$S-Y$的绝对值最小的$Y$只可能是两种,一种是$<S$的最大的$Y$,一种是$>S$的最小的$Y$.那就分别求出来叭.分别求的时候这个$W$的值是可以二分的.但是这样并不能$A$掉这题,因为$check$的复杂度仍然是$O(NM)$的.看了题解之后发现$check$可以用前缀和吖,觉得很巧妙$qwq$.这样下来$check()$的复杂度变成$O(N+M).$
$Code$
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define il inline #define Rg register #define go(i,a,b) for(Rg int i=a;i<=b;++i) #define yes(i,a,b) for(Rg int i=a;i>=b;--i) #define mem(a,b) memset(a,b,sizeof(a)) #define int long long #define db double #define inf 2147483647 using namespace std; il int read() { Rg int x=0,y=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();} return x*y; } const int N=200010; int n,m,S,as,minw=inf,maxw,sn[N],sv[N]; struct nd1{int w,v;}a[N]; struct nd2{int l,r;}b[N]; il int calc(int x) { Rg int ret=0; mem(sn,0);mem(sv,0); go(i,1,n) if(a[i].w>=x)sn[i]=sn[i-1]+1,sv[i]=sv[i-1]+a[i].v; else sn[i]=sn[i-1],sv[i]=sv[i-1]; go(i,1,m) { Rg int l=b[i].l,r=b[i].r; ret+=(sn[r]-sn[l-1])*(sv[r]-sv[l-1]); } return ret; } il int ef1() { Rg int l=minw,r=maxw,mid,y,ret; while(l<=r) { mid=(l+r)>>1; y=calc(mid); if(y<=S)ret=y,r=mid-1; else l=mid+1; } return ret; } il int ef2() { Rg int l=minw,r=maxw,mid,y,ret; while(l<=r) { mid=(l+r)>>1; y=calc(mid); if(y>=S)ret=y,l=mid+1; else r=mid-1; } return ret; } main() { n=read(),m=read(),S=read(); go(i,1,n)a[i]=(nd1){read(),read()},minw=min(minw,a[i].w),maxw=max(maxw,a[i].w); go(i,1,m)b[i]=(nd2){read(),read()}; Rg int y1=ef1(),y2=ef2(); as=min(abs(y1-S),abs(y2-S)); printf("%lld\n",as); return 0; }