MnZn 55pts求助
查看原帖
MnZn 55pts求助
232507
OK咯莫名其妙楼主2021/11/15 15:38
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int maxx=-2e9;
struct node{
	int w,v;
}a[200005];
int s[200005];
int cnt[200005];
int n,m,y;
int flag=0;
int lef[200005],righ[200005];
int check(int k){
	memset(s,0,sizeof(s));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++)
	{
		if(a[i].v>=k){
			s[i]=s[i-1]+a[i].w;
			cnt[i]=cnt[i-1]+1;
		}
		else
		{
			s[i]=s[i-1];
			cnt[i]=cnt[i-1];
		}
	}
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		sum+=(cnt[righ[i]]-cnt[lef[i]-1])*(s[righ[i]]-s[lef[i]-1]);
	}
	if(sum>y)return true;
	if(sum<y)return false;
	if(sum==0){
		flag=1;
		return true;
	}
}
signed main(){
//	freopen("P1314_4.in","r",stdin);
	cin>>n>>m>>y;
	for(int i=1;i<=n;i++){
		cin>>a[i].v>>a[i].w;
		maxx=max(maxx,a[i].v);	
	}
	for(int i=1;i<=m;i++)
	{
		cin>>lef[i]>>righ[i];
	}
	int l=0,r=maxx;
	while(l<=r){
		int mid=(l+r+1)>>1;
		if(flag==1){
			cout<<0<<endl;
			return 0;
		}
		else
		{
			if(check(mid))l=mid+1;
			else
			r=mid-1;
		}
	}
	int ans=0;
	l=l-1;
	for(int i=1;i<=m;i++)
	{
		int num=0;
		int tmp=0;
		for(int j=lef[i];j<=righ[i];j++)
		{
			if(a[j].v>=l){
				num++;
				tmp+=a[j].w;
			}
			else
			continue;
		}
		ans+=num*tmp;
	}
	cout<<ans-y<<endl;
	return 0;
}
2021/11/15 15:38
加载中...