200. 교차 개수 세기

백준

<교차점 세기>

Python

<시간 초과>

def update(index, value):
	while index <= n:
		tree[index] += value
		index += index & -index

def query(index):
	ans = 0
	while index:
		ans += tree[index]
		index -= index & -index

	return ans

tree = [0] * 2001
n, m = map(int, input().split())
edge = []
ans = 0

for _ in range(m):
  a, b = map(int, input().split())
  edge.append((a, b))

edge.sort()

for A, B in edge:
  ans += query(n) - query(B)
  update(B, 1);

print(ans)

C++

참고

#include <bits/stdc++.h>
using namespace std;
 
long long ans;
int n, m, a,b;
vector <pair<int, int>> edge;
int tree[2001];
 
void update(int idx, int val) {
    while (idx <= n) {
        tree[idx] += val;
        idx += idx & -idx;
    }
}
 
int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += tree[idx];
        idx -= idx & -idx;
    }
    return ret;
}
 
int main() {
    scanf("%d%d", &n, &m);
    while(m--) {
        scanf("%d%d", &a, &b);
        edge.push_back(make_pair(a, b));
    }
    sort(edge.begin(), edge.end());
 
    for (auto [A, B] : edge) {
        ans += query(n) - query(B);
        update(B,1);
    }
    printf("%lld", ans);
    return 0;
}