티스토리 뷰

알고리즘 관련/BOJ

BOJ)5419 북서풍

JASON 자손9319 2017. 1. 10. 17:32

문제: icpc.me/5419


북서풍을 타고 항해할 수 있는 섬의 쌍의 개수를 구하는 문제이다.


여기서 북서풍을 타고 항해할 수 있는 섬이란 어떤 섬 기준으로 x좌표가 해당하는 섬보다 크거나 같고 y좌표가 해당하는 섬보다 작거나 같은 섬들을 말한다.


결국 우리는 각 섬마다 x좌표가 작으면서 y좌표는 큰 섬들의 개수를 구한 뒤 그 합을 출력하면 된다.


우리는 x좌표가 작은 수를 우선적으로 정렬하되 x좌표가 같을 경우 y좌표가 큰 수를 우선적으로 정렬을 할 것이다.


이렇게 정렬을 했을 시에 먼저 등장하는 좌표뒤에 나오는 좌표들 중 북서풍을 타고 항해할 수 있는 섬이 없다는 것은 자명하다.


따라서 우리는 정렬을 해준 뒤 순서대로 봐주면 된다.


x좌표 기준으로 정렬을 했으므로 우리는 먼저 등장했던 섬들 중에서 y좌표가 내가 현재 보고 있는 섬보다 큰 섬들의 개수만 세주면 된다.


이는 세그먼트 트리를 이용하여 구해줄 수 있는데 이때 좌표가 10^9까지 등장하기 때문에 좌표를 노드로 만들기에는 무리가 있다.


따라서 우리는 좌표 압축 기법을 사용하여 y좌표를 좌표 압축 해준 뒤 인덱스를 얻어 세그먼트 트리에 업데이트 시켜준 후 현재 보고 있는 섬보다 큰 y좌표의 개수를 구해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX_N 100000
using namespace std;
int t, n, x, y, seg[* MAX_N], b[MAX_N];
pair<int,int> a[MAX_N + 1];
bool cmp(pair<intint> x, pair<intint> y) {
    if (x.first == y.first)
        return x.second > y.second;
    return x.first < y.first;
}
int update(int pos, int val, int node, int x, int y) {
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    int mid = (x + y) >> 1;
    return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&<= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * + 1, mid + 1, y);
}
int main() {
    scanf("%d"&t);
    while (t--) {
        memset(seg, 0sizeof(seg));
        memset(b, 0sizeof(b));
        long long res = 0;
        scanf("%d"&n);
        vector<int> ypos;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d"&x, &y);
            a[i] = { x,y };
            ypos.push_back(y);
        }
        sort(a + 1, a + n + 1, cmp);
        sort(ypos.begin(), ypos.end());
        ypos.erase(unique(ypos.begin(), ypos.end()), ypos.end());
        for (int i = 1; i <= n; i++) {
            int z = lower_bound(ypos.begin(), ypos.end(), a[i].second) - ypos.begin();
            res += (long long)query(z, n - 110, n - 1);
            b[z]++;
            update(z, b[z], 10, n - 1);
        }
        printf("%lld\n", res);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)3653 영화 수집  (0) 2017.01.10
BOJ)6549 히스토그램에서 가장 큰 직사각형  (0) 2017.01.10
BOJ)5419 북서풍  (7) 2017.01.10
BOJ)1849 순열  (0) 2017.01.10
BOJ)4195 친구 네트워크  (0) 2017.01.10
BOJ)9345 디지털 비디오 디스크(DVDs)  (0) 2017.01.10
댓글
댓글쓰기 폼