반응형

https://www.acmicpc.net/problem/3770

 

3770번: 대한민국

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. pair < int, int > arr [ 400001 ]를 만들어 수를 입력받고, arr배열을 오름차순으로 정렬합니다.

 

2. for문을 통해 반복하면서 arr[ i ].second를 idx로 세그먼트 트리를 갱신하고, arr [ i ].second + 1부터 M까지의 구간 합을 구해 ans에 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#define ll long long
 
using namespace std;
 
int T;
pair<int, int> arr[400001];
 
void updateTree(int node, int s, int e, int idx, ll* segTree)
{
    if (idx < s || e < idx) return;
    segTree[node]++;
 
    if (s != e) {
        int m = (s + e) / 2;
        updateTree(node * 2, s, m, idx, segTree);
        updateTree(node * 2 + 1, m + 1, e, idx, segTree);
    }
}
 
ll sumTree(int node, int s, int e, int sidx, int eidx, ll* segTree)
{
    if (sidx > e || eidx < s) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = sumTree(node * 2, s, m, sidx, eidx, segTree);
    ll right = sumTree(node * 2 + 1, m + 1, e, sidx, eidx, segTree);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &T);
 
    for (int t = 1; t <= T; t++) {
        int N, M, K;
        ll segTree[2050] = { 0 };
        scanf("%d %d %d", &N, &M, &K);
 
        for (int i = 0; i < K; i++) {
            scanf("%d %d", &arr[i].first, &arr[i].second);
        }
 
        sort(arr, arr + K);
 
        ll ans = 0;
 
        for (int i = 0; i < K; i++) {
            updateTree(1, 1, M, arr[i].second, segTree);
            ans += sumTree(1, 1, M, arr[i].second + 1, M, segTree);
        }
 
        printf("Test case %d: %lld\n", t, ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 9463번 - 순열 그래프 (C++)  (0) 2023.01.23
[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21

+ Recent posts

티스토리툴바