70分求调
查看原帖
70分求调
1232696
zbbfans楼主2024/9/28 20:19
#include<bits/stdc++.h>
#define int long long
using namespace std;
int w[200010],v[200010];
int l[200010],r[200010];
int sumw[200010],sumv[200010];
int n,m,s;
int ll,rr,ans=1e11;
bool check(int x){
	for(int i=0;i<=n;i++){
		sumw[i]=0;
		sumv[i]=0;
	}
	for(int i=1;i<=n;i++){
		if(x<=w[i]){
			sumw[i]=sumw[i-1]+1;
			sumv[i]=sumv[i-1]+v[i];
		}else{
			sumw[i]=sumw[i-1];
			sumv[i]=sumv[i-1];
		}
	}
	int y=0;
	for(int i=1;i<=m;i++){
		y+=(sumw[r[i]]-sumw[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
	}
	if(y<s) return false;
	else return true; 
}
signed main(){
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
		rr=max(rr,w[i]);
	}
	for(int i=1;i<=m;i++){
		cin>>l[i]>>r[i];
	}
	while(ll<=rr){
		int mid=(ll+rr)/2;
		if(check(mid)){
			ans=mid;
			ll=mid+1;
			//cout<<1<<endl;
		}else{
			rr=mid-1;
			//cout<<2<<endl;
		}
	}
	for(int i=0;i<=n;i++){
		sumw[i]=0;
		sumv[i]=0;
	}
	for(int i=1;i<=n;i++){
		if(w[i]>=ans){
			sumw[i]=sumw[i-1]+1;
			sumv[i]=sumv[i-1]+v[i];
		}else{
			sumw[i]=sumw[i-1];
			sumv[i]=sumv[i-1];
		}
	}
	int sum=0;
	for(int i=1;i<=m;i++){
		sum+=(sumw[r[i]]-sumw[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
	}
	cout<<abs(sum-s);
	return 0;
} 


2024/9/28 20:19
加载中...