啊啊啊,为什么错了
查看原帖
啊啊啊,为什么错了
910357
songzhihan2010楼主2024/7/8 17:00
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const ll N=2e4+10;
ll n;
struct Node{
	ll v,x;
}a[N];
ll ans=0;
bool cmp2(Node x,Node y){
	return x.x<y.x;
}
void cdq(ll l,ll r){
	if(l==r) return ;
	ll mid=(l+r)/2;
	cdq(l,mid);
	cdq(mid+1,r);
	sort(a+l,a+mid+1,cmp2);//左闭右不闭 
	sort(a+mid+1,a+r+1,cmp2);
	ll cnt1=0,cnt2=0;
	for (int i=l;i<=mid;i++){
		cnt1+=a[i].x;
	}
	for(int i=mid+1,j=l;i<=r;i++){
		while(j<=mid&&a[j].x<a[i].x)
			cnt1-=a[j].x,cnt2+=a[j].x,j++;
		ans+=a[i].v*((j-1)*a[i].x-cnt2+cnt1-(mid-j+1)*a[i].x);
	}
}
bool cmp1(Node x,Node y){
	return x.v<y.v;
}
signed main(){
	n=read();
	for (int i=1;i<=n;i++){
		a[i].v=read();
		a[i].x=read();
	}
	sort(a+1,a+1+n,cmp1);
	cdq(1,n);
	cout<<ans;
}

非常谢谢

2024/7/8 17:00
加载中...