爆零,dalao求条
查看原帖
爆零,dalao求条
957917
ljkgs6789楼主2024/11/9 22:36
#include<bits/stdc++.h>
using namespace std;
int n,pre[50010],ans;
struct node{
	int v,x;
}a[50010];
bool cmp(node x,node y){
	return x.v<y.v;
}
bool cmp1(node x,node y){
	if(x.x==y.x)return x.v<y.v;
	return x.x<y.x;
}
void cdq(int L,int R){
	if(L>=R)return ;
	int mid=L+R>>1;
	cdq(L,mid);
	cdq(mid+1,R);
	sort(a+mid+1,a+R+1,cmp1);
	sort(a+L,a+mid+1,cmp1);
	memset(pre,0,sizeof(pre));
	for(int i=L;i<=R;i++)pre[i]=pre[i-1]+a[i].x;
	int i=L-1;
	for(int j=mid+1;j<=R;j++){
		if(i<mid&&a[i+1].x<=a[j].x){
			i++;
		}
		ans+=a[j].v*(a[j].x*(i-L+1)-pre[i]+pre[mid]-pre[i]-a[j].x*(mid-i));
	}
	return ;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].v>>a[i].x;
	}
	sort(a+1,a+1+n,cmp);
	cout<<ans;
	return 0;
}
2024/11/9 22:36
加载中...