01:42:24
최소값을 저장하는 세그먼트 트리를 사용하는데 그냥 사용하면 안 되고 발상의 전환이 필요하다.
모든 학생들의 번호를 1번 시험의 등수로 바꾼다.
예를 들면, 1번 시험의 등수가 2 3 1 이면, 2등한 학생이 1번 학생이 되는 식이다.
학생 번호를 1번 시험의 결과로 바꿨으니 1번 시험은 더 이상 신경쓰지 않는다.
만약 시험이 3개가 아니라 2개만 있다고 가정하고 다음과 같은 예시를 보자.
학생 번호: 1 2 3 4
2번 시험 등수: 3 1 2 4
학생 번호 순서대로 2번 시험 등수에 방문한다고 하자. 이때 해당 등수에 방문하면 true값을 저장한다고 하자.
2번 학생을 보았을 때, 2번 시험 등수 기준으로 자신보다 앞 등수이면서 방문이 true인 학생 1번이 있다. 즉 1번 학생은 2번학생보다 1번시험, 2번시험 모두 등수가 높다는 뜻이다. 따라서 2번 학생은 굉장한 학생이 될 수 없다.
이를 일반화시키면 학생 번호 순서대로 방문하는데 2번 시험 등수 기준으로 자신보다 앞 등수인데 먼저 방문한 학생이 있으면 해당 학생은 굉장한 학생이 될 수 없다.
그런데 이를 시험 3개에 대해서 적용시키려면 어떻게 해야 할까?
방문에 true/false가 아니라 3번 시험의 등수를 넣으면 된다. 예시를 보자.
학생 번호: 1 2 3 4
2번 시험 등수: 3 1 2 4
3번 시험 등수: 4 2 3 1
여전히 학생번호가 1번 시험 등수로 바뀌었으므로 1번 시험은 신경 쓸 필요가 없다.
다시 2번 학생의 경우를 보자. 이번엔 방문할 때 true가 아니라 해당 학생의 3번 시험 등수를 넣는 것이다.
2번 학생이 2번 시험 등수를 방문했을 때 2번학생보다 앞인 학생 중에 방문한 학생은 1번 학생만 존재하고 1번 학생이 방문하면서 저장한 값은 1번 학생의 3번 시험 등수인 4등이 된다. 반면에 2번 학생의 3번 시험 결과는 2등이다.
따라서 (1번 학생의 값 4) > (2번 학생의 값 2) 이므로 이는 1번 학생이 2번 학생보다 1번 시험, 2번 시험에서는 앞섰지만 3번시험에서는 뒤쳐졌다는 것을 알 수 있다.
이를 일반화시키면 학생 번호 순서대로 방문하는데 자신보다 앞 등수들에 대해 최솟값이 현재 학생의 3번 시험 등수보다 작으면 현재 학생보다 1,2,3번 시험 전부가 등수가 좋은 학생이 존재한다는 말이 된다.
이를 코드로 작성하면 다음과 같다.
#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#define INF 987654321
#define INF2 2147483647
#define f first
#define s second
#define x first
#define y second
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ti3 = tuple<int, int, int>;
class segment {
public:
vector<ll> tree; //tree[node] := a[start ~ end] 의 합
segment() {}
segment(int size) {
this->resize(size);
}
void resize(int size) {
size = (int) floor(log2(size)) + 2;
size = pow(2, size);
tree.resize(size, INF);
}
ll MIN(int node, int start, int end, int left, int right) {
if(right < start || end < left) return INF;
if(left <= start && end <= right) return tree[node];
return min(MIN(node * 2, start, (start + end) / 2, left, right),
MIN(node * 2 + 1, (start + end) / 2 + 1, end, left, right));
}
ll update(int node, int start, int end, int index, ll value) {
if(index < start || end < index) return tree[node];
if(start == end) return tree[node] = value;
return tree[node] = min(update(node * 2, start, (start + end) / 2, index, value),
update(node * 2 + 1, (start + end) / 2 + 1, end, index, value));
}
};
struct Student {
int testRank[4];
Student() {}
bool operator<(Student other) const {
return testRank[1] < other.testRank[1];
}
};
int N;
vector<Student> studentInfo;
vector<bool> notAwesome;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
segment root(N);
studentInfo.resize(N + 1);
notAwesome.resize(N + 1, false);
for(int tn=1; tn<=3; tn++) {
for(int i=1; i<=N; i++) {
int student; cin >> student;
studentInfo[student].testRank[tn] = i;
}
}
sort(all(studentInfo));
for(int student=1; student<=N; student++) {
if(root.MIN(1, 1, N, 1, studentInfo[student].testRank[2]) < studentInfo[student].testRank[3]) notAwesome[student] = true;
root.update(1, 1, N, studentInfo[student].testRank[2], studentInfo[student].testRank[3]);
}
int ans = 0;
for(int i=1; i<=N; i++) ans += !notAwesome[i];
cout << ans << '\n';
return 0;
}