2336 굉장한 학생 https://www.acmicpc.net/problem/2336
각 사람마다 communication skills, programming skills, algorithmic knowledge가 등수로 주어진다.
어떤 사람의 세 가지 등수보다 모두 높은 등수를 가진 사람이 존재하면 그사람을 추천해서는 안된다.
사람들의 등수가 주어질 때 추천할 수 있는 사람의 수를 구하는 문제이다.
세 등 수중 앞의 등수를 기준으로 정렬하면 차원 하나를 줄일 수 있다.
그 후에 segment tree로 관리를 해주면서 값을 갱신해나가면 된다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
const int MAXN = 1e5 + 5;
struct Save { int a, b, c; };
int t, n;
Save save[MAXN];
struct Segment {
int sze;
vector<int> tree;
Segment() {}
Segment(int s) :sze(s) { tree.resize(4 * s, INF); }
int update(int idx, int val, int node, int nl, int nr) {
if (nr < idx || nl > idx) return tree[node];
if (nl == nr) return tree[node] = val;
int mid = (nl + nr) >> 1;
return tree[node] = min(update(idx, val, node * 2, nl, mid), update(idx, val, node * 2 + 1, mid + 1, nr));
}
void update(int idx, int val) {
update(idx, val, 1, 0, sze - 1);
}
int query(int l, int r, int node, int nl, int nr) {
if (r < nl || l > nr) return INF;
if (l <= nl && nr <= r) return tree[node];
int mid = (nl + nr) >> 1;
return min(query(l, r, node * 2, nl, mid), query(l, r, node * 2 + 1, mid + 1, nr));
}
int query(int l, int r) {
return query(l, r, 1, 0, sze - 1);
}
};
int main() {
scanf("%d",&t);
while (t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d%d%d", &save[i].a, &save[i].b, &save[i].c);
sort(save, save + n, [](Save &a, Save &b)->bool {
return a.a < b.a;
});
Segment seg(n + 1);
int ans = n;
for (int i = 0; i < n; i++) {
int mn = seg.query(0, save[i].b - 1);
if (mn < save[i].c) ans--;
seg.update(save[i].b, save[i].c);
}
printf("%d\n", ans);
}
return 0;
}
| cs |
