Submission #5862

#	Time	Username	Problem	Language	Result	Execution time	Memory
5862		cki86201	사회적 불평등 (TOKI14_social)	C++98	100 / 100	52 ms	2180 KiB

social

#include<stdio.h>
#include<algorithm>

#define X first
#define Y second
typedef long long ll;
typedef std::pair<int,int> Pi;

const int ML = 10001;

int n;
Pi inp[100010];
struct BIT{
	static const int N_ = 10010;
	ll T[N_];
	void update(int x,int v){for(int i=x;i;i-=(i&-i))T[i] += v;}
	void update(int x0,int x1,int v){update(x1,v),update(x0-1,-v);}
	ll read(int x){
		ll res = 0;
		for(int i=x;i&&i<N_;i+=(i&-i))res += T[i];
		return res;
	}
};

struct BIT2{
	BIT T0, T1;
	void update(int x,int a){
		T0.update(x+1, ML, -x*a);
		T0.update(1, x, x*a);
		T1.update(x+1, ML, a);
		T1.update(1, x, -a);
	}
	ll read(int x){
		return T0.read(x) + T1.read(x) * x;
	}
}tr[2];

ll ans;

int main()
{
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)scanf("%d%d",&inp[i].X,&inp[i].Y);
	std::sort(inp,inp+n);
	for(i=0;i<n;i++){
		tr[0].update(inp[i].Y, ML - inp[i].X);
		tr[1].update(inp[i].Y, 1);
		ans += tr[0].read(inp[i].Y) - tr[1].read(inp[i].Y) * (ML - inp[i].X);
	}
	printf("%lld",ans);
	return 0;
}

• Subtask 1: 29 / 29
• Subtask 2: 19 / 19
• Subtask 3: 20 / 20
• Subtask 4: 32 / 32