백준5419 북서풍

작성일 | In

문제 링크

  • http://icpc.me/5419

문제 출처

  • 2005 BAPC E번

사용 알고리즘

  • Segment Tree

시간복잡도

  • O(NlogN)

풀이

Nlog2N은 TLE가 납니다.

남쪽에 있는 점이 앞에 오도록, 동쪽에 있는 점이 앞에 오도록 정렬을 해줍니다.
자신보다 앞에 있는 점들은 모두 남쪽에 있으므로 점들을 하나씩 세그먼트 트리에 넣어주면서 자신보다 동쪽에 있는 점의 개수를 카운팅하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

vector<ll> i_pos, j_pos;
vector<p> v;

void compress(){
	sort(i_pos.begin(), i_pos.end());
	i_pos.erase(unique(i_pos.begin(), i_pos.end()), i_pos.end());
	sort(j_pos.begin(), j_pos.end());
	j_pos.erase(unique(j_pos.begin(), j_pos.end()), j_pos.end());
	for (int i = 0; i < v.size(); i++){
		v[i].x = lower_bound(i_pos.begin(), i_pos.end(), v[i].x) - i_pos.begin();
		v[i].y = lower_bound(j_pos.begin(), j_pos.end(), v[i].y) - j_pos.begin();
	}
}

ll tree[404040];
int bias = 1 << 17;

void update(int x, ll v){
	x += bias; tree[x] += v;
	while (x >>= 1){
		tree[x] = tree[x << 1] + tree[x << 1 | 1];
	}
}

ll query(ll l, ll r){
	l += bias, r += bias;
	ll ret = 0;
	while (l < r){
		if (l & 1) ret += tree[l++];
		if (~r & 1) ret += tree[r--];
		l >>= 1, r >>= 1;
	}
	if (l == r) ret += tree[r];
	return ret;
}

void init(){
	memset(tree, 0, sizeof tree);
	i_pos.clear(), j_pos.clear();
	v.clear();
}

void solve(){
	init();
	int n; cin >> n;
	for (int i = 0; i < n; i++){
		ll a, b; cin >> a >> b;
		v.push_back({ a, -b });
		i_pos.push_back(a);
		j_pos.push_back(-b);
	}
	compress();
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());

	long long ans = 0;
	for (auto i : v){
		ans += query(i.y, 100000);
		update(i.y, 1);
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) solve();
}