oj.uz

Submission #5863

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

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2020 KB Output is correct
2 Correct 16 ms 1888 KB Output is correct
3 Correct 12 ms 1884 KB Output is correct
4 Correct 12 ms 1884 KB Output is correct
5 Correct 16 ms 2056 KB Output is correct
6 Correct 16 ms 2028 KB Output is correct
7 Correct 12 ms 1884 KB Output is correct
8 Correct 16 ms 1884 KB Output is correct
9 Correct 16 ms 1884 KB Output is correct
10 Correct 16 ms 2016 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1884 KB Output is correct
2 Correct 16 ms 2016 KB Output is correct
3 Correct 16 ms 2016 KB Output is correct
4 Correct 12 ms 2016 KB Output is correct
5 Correct 16 ms 2016 KB Output is correct
6 Correct 12 ms 2056 KB Output is correct
7 Correct 16 ms 2140 KB Output is correct
8 Correct 16 ms 2028 KB Output is correct
9 Correct 8 ms 1884 KB Output is correct
10 Correct 16 ms 2016 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1884 KB Output is correct
2 Correct 32 ms 2280 KB Output is correct
3 Correct 32 ms 2032 KB Output is correct
4 Correct 20 ms 2016 KB Output is correct
5 Correct 20 ms 2016 KB Output is correct
6 Correct 36 ms 2280 KB Output is correct
7 Correct 28 ms 2148 KB Output is correct
8 Correct 36 ms 2412 KB Output is correct
9 Correct 48 ms 2544 KB Output is correct
10 Correct 52 ms 2544 KB Output is correct