PS Diary #8
BOJ 2517. 달리기segment tree, coordinate compression 보자마자 세그먼트 트리가 떠올라야하는 문제이다. 어떤 선수의 최소 등수는 $($그 선수 앞에 있는 선수들 중 그 선수보다 실력이 좋은 선수들 명수$) + 1$ 등이 된다. 그래서 앞에서 부터 segment tree에 업데이트 해주며 계산해주면 된다. 또한 선수들 실력의 절대적인 값은 중요하지 않으므로 좌표 압축을 해주어야한다. 시간복잡도는 $O(N\log{}{N})$이다.더보기#include #define fastio cin.tie(0)->ios::sync_with_stdio(0);using namespace std;const int NMAX = 5e5;int N;vector skill_level, cmp;struc..
Computer Science
2025. 2. 16. 13:48