题解

说个事，这题在锣鼓只是个绿题
二分+前缀和轻松AC

#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+5;
struct Data{
	int l,r;
}e[N];
int n,m;
long long w[N],v[N];
long long s1[N],s2[N];
long long A(long long x) {
	s1[0]=s2[0]=0;
	for (int i=1;i<=n;i++) {
		s1[i]=s1[i-1];
		s2[i]=s2[i-1];
		if (w[i]>=x) {
			s1[i]++;
			s2[i]+=v[i];
		}
	}
	long long sum=0;
	for (int i=1;i<=m;i++) {
		sum+=(s1[e[i].r]-s1[e[i].l-1])*(s2[e[i].r]-s2[e[i].l-1]);
	}
	return sum;
}
int main() {
	long long s,L=1e18,R=-1e18;
	scanf("%d %d %lld",&n,&m,&s);
	for (int i=1;i<=n;i++) {
		scanf("%d %d",&w[i],&v[i]);
		L=min(L,w[i]);
		R=max(R,w[i]);
	}
	for (int i=1;i<=m;i++) {
		scanf("%d %d",&e[i].l,&e[i].r);
	}
	L++,R++;
	long long l=L,r=R,ans1=-1e18,ansk1=-1;
	while (l<=r) {
		long long mid=(l+r)>>1;
		long long k=A(mid);
		if (k>=s) {
			ans1=max(ans1,mid);
			ansk1=k;
			l=mid+1;
		}else {
			r=mid-1;
		}
	}
	l=L,r=R;
	long long ans2=1e18,ansk2=-1;
	while (l<=r) {
		long long mid=(l+r)>>1;
		long long k=A(mid);
		if (k<=s) {
			ans2=min(ans2,mid);
			ansk2=k;
			r=mid-1;
		}else {
			l=mid+1;
		}
	}
	if (ans1!=-1e18&&ans2==1e18) {
		printf("%lld",ansk1-s);
	}else if (ans1==-1e18&&ans2!=1e18) {
		printf("%lld",s-ansk2);
	}else {
		long long Ans1=ansk1-s;
		long long Ans2=s-ansk2;
		printf("%lld",min(Ans1,Ans2));
	}
	return 0;
}