백준 9426 중앙값 측정 혼내주기
온도가 0부터 216이기 때문에 리프 노드가 온도인 세그 트리를 만들고 k개를 유지하면서 (k+1)/2번째 수를 찾는 쿼리를 날리면 된다. 매번 삭제와 추가를 반복해도 어차피 모든 연산이 O(log(n))이기 때문에 충분히 가능하다. #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[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1 K; for(int i =..
혼내주기
2021. 7. 21. 12:15