[백준 BOJ][세그먼트 트리] 2336 굉장한 학생

2336_굉장한 학생

링크

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

 

풀이

 

시험을 3번 치룹니다. 어떤 학생보다 대단한 학생이 없어야 그 학생이 굉장한 학생입니다.

 

학생은 1~N 순서대로 번호가 부여되기 때문에, 첫 번째 등수를 기준으로 정렬을 합니다.

그럼 정렬을 한 상태에서 i번째 학생이 굉장하려면 1~i-1번째 학생 중에 대단한 학생을 찾으면 됩니다. 왜냐하면 i+1~N번째 학생은 이미 첫 번째 시험에서 밀렸기 때문이죠.

 

그럼 2번째 등수와 3번째 등수가 남았는데, 2번째 등수를 세그먼트 트리의 인덱스로 놓고 3번째 등수를 값으로 저장하게 합니다.

 

그 다음 1 ~ 2번째 등수 - 1에서 값의 최솟값을 뽑으면 나보다 2번째 등수가 높은 사람들 중에 3번째 등수의 최솟값이 나옵니다. 만약 이 등수보다 내 등수가 안 나왔다? 그러면 i번째 학생보다 1,2,3번째 시험 모두 다 잘 본 학생이 존재한다는 말이겠죠?

 

이렇게 count를 잘 해서 출력을 하면 됩니다.

 

코드

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

//2336_굉장한 학생 #include <cstdio> #include <algorithm> #include <vector> #define MAX 500001 using namespace std;   int n, ans, tmp; int a[MAX], b[MAX], c[MAX]; int tree[MAX * 4]; vector<pair<int, pair<int, int>>> v;   int init(int node, int start, int end) {     if (start == end)         return tree[node] = 1e9;     else         return tree[node] = max(init(node * 2, start, (start + end) / 2), init(node * 2 + 1, (start + end) / 2 + 1, end)); }   void update(int node, int start, int end, int index, int val) {     if (index < start || index > end) return;     if (start == end) {         tree[node] = val;         while (node >= 1) {             node /= 2;             tree[node] = min(tree[node * 2], tree[node * 2 + 1]);         }         return;     }     else {         update(node * 2, start, (start + end) / 2, index, val);         update(node * 2 + 1, (start + end) / 2 + 1, end, index, val);     } }   int findMin(int node, int start, int end, int left, int right) {     if (left > end || right < start) return 1e9;     else if (left <= start && right >= end) return tree[node];     return min(findMin(node * 2, start, (start + end) / 2, left, right), findMin(node * 2 + 1, (start + end) / 2 + 1, end, left, right)); }   int main() {     scanf("%d", &n);     for (int i = 0; i < MAX * 4; ++i) tree[i] = 1e9;       v.push_back(make_pair(0, make_pair(0, 0)));     for (int i = 1; i <= n; ++i) scanf("%d", &tmp), a[tmp] = i;     for (int i = 1; i <= n; ++i) scanf("%d", &tmp), b[tmp] = i;     for (int i = 1; i <= n; ++i) scanf("%d", &tmp), c[tmp] = i;     for (int i = 1; i <= n; ++i) v.push_back(make_pair(a[i], make_pair(b[i], c[i])));       sort(v.begin(), v.end());       //for (int i = 1; i <= n; ++i) printf("%d %d %d\n", v[i].first, v[i].second.first, v[i].second.second);       //2번째 값을 인덱스로, 3번째 값을 갖는 세그먼트 트리를 구성     //i번째가 굉장한 학생이려면 세그트리에서 (1 ~ i의 두 번째 값-1)까지의 최솟값이 i의 3번째 값보다 커야함       for (int i = 1; i <= n; ++i) {         if (findMin(1, 1, n, 1, v[i].second.first - 1) > v[i].second.second) ans++;         update(1, 1, n, v[i].second.first, v[i].second.second);     }       printf("%d\n", ans);       return 0; } Colored by Color Scripter

cs