백준 2517 달리기 혼내주기
머지소트트리로 풀었는데, 좌표를 압축해서 그냥 세그로 풀면 메모리를 훨씬 줄일 수 있어서 다시 풀었다. 능력의 범위는 10억까지지만 총 갯수는 500000이므로 좌표 압축을 하고 각각이 leaf인 세그를 만든다. 이후 들어온 사람 순서대로 [0,자신의능력) 구간에 몇명이나 있는지 쿼리를 날리고 매번 해당 사람을 update 해주면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1};..
혼내주기
2021. 7. 22. 10:56