Submission #5863

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

social

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

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

const int ML = 10001;

int n;
std::vector <int> v[10010];
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++){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	for(int u=1;u<ML;u++){
		for(i=0;i<v[u].size();i++){
			int t = v[u][i];
			tr[0].update(t, ML - u);
			tr[1].update(t, 1);
			ans += tr[0].read(t) - tr[1].read(t) * (ML - u);
		}
	}
	printf("%lld",ans);
	return 0;
}

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