oj.uz

Submission #5862

# Submission time Handle Problem Language Result Execution time Memory
5862 2014-05-20T10:44:01 Z cki86201 사회적 불평등 (TOKI14_social) C++
100 / 100
 52 ms 2180 KB 
#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.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 0 ms 2180 KB Output is correct
6 Correct 0 ms 2180 KB Output is correct
7 Correct 0 ms 2180 KB Output is correct
8 Correct 0 ms 2180 KB Output is correct
9 Correct 0 ms 2180 KB Output is correct
10 Correct 0 ms 2180 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2180 KB Output is correct
2 Correct 20 ms 2180 KB Output is correct
3 Correct 16 ms 2180 KB Output is correct
4 Correct 16 ms 2180 KB Output is correct
5 Correct 20 ms 2180 KB Output is correct
6 Correct 20 ms 2180 KB Output is correct
7 Correct 12 ms 2180 KB Output is correct
8 Correct 16 ms 2180 KB Output is correct
9 Correct 12 ms 2180 KB Output is correct
10 Correct 20 ms 2180 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2180 KB Output is correct
2 Correct 20 ms 2180 KB Output is correct
3 Correct 20 ms 2180 KB Output is correct
4 Correct 16 ms 2180 KB Output is correct
5 Correct 16 ms 2180 KB Output is correct
6 Correct 16 ms 2180 KB Output is correct
7 Correct 20 ms 2180 KB Output is correct
8 Correct 20 ms 2180 KB Output is correct
9 Correct 12 ms 2180 KB Output is correct
10 Correct 24 ms 2180 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2180 KB Output is correct
2 Correct 48 ms 2180 KB Output is correct
3 Correct 40 ms 2180 KB Output is correct
4 Correct 20 ms 2180 KB Output is correct
5 Correct 28 ms 2180 KB Output is correct
6 Correct 40 ms 2180 KB Output is correct
7 Correct 28 ms 2180 KB Output is correct
8 Correct 44 ms 2180 KB Output is correct
9 Correct 52 ms 2180 KB Output is correct
10 Correct 52 ms 2180 KB Output is correct