Approach 상당히 재밌는 문제이다. 문제를 요약하자면, 3개의 시험에 대해서 모두 다 우월한 학생이 있는지를 판단하는 것이 굉장히 중요하다. 일단 첫번째 시험을 기준으로 오름차순으로 정렬을 한다. 정렬된 결과에서 앞에 위치하는 학생은 적어도 첫번째 시험을 더 잘 본 것이므로, 해당 학생보다 뒤에 위치하는 학생은 굉장한 학생한 학생을 판단하는 과정에서 고려하지 않아도 된다. 따라서 첫 시험을 기준으로 정렬을 한 뒤, 해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 학생이 없다면 해당 학생은 굉장한 학생이라고 판단해주면 된다. 따라서, 이 문제를 풀기 위해서 실질적으로 해결해야하는 부분은 "해당 학생의 앞에 있는 학생 중 2, 3번째 시험을 모두 더 잘 본 사람이 있는지 여부"이다...

Approach 일단 처음 접근한 방법은 세그먼트 트리 + 이분 탐색이다. 잘 생각해보면 bitwise or 계산 결과는 단조증가할 수 밖에 없다. 구간의 시작점을 1 ~ N까지 이동시키면서, lower_bound를 해서 k가 나오면 해당 구간을 출력해주면 된다. 구간 별 xor 결과는 세그먼트 트리를 통해서 관리를 하고, 이를 이분탐색으로 만족하는 구간이 있는지를 파악해주면 된다. 대회가 끝나고 공식 해설을 보고, 다음과 같은 방법으로 풀면 좀 더 쉽게 처리할 수 있음을 파악하였다. 잘 생각해보면, k와 xor한 결과가 k이면 구간 안에 들어갈 수 있는 수이고, 그렇지 않으면 무조건 들어갈 수 없는 수이다. 따라서, 들어갈 수 있는 숫자들을 전부 다 더했을 때 k가 나오면 문제조건을 만족할 수 있는 구..

Approach 자기보다 아래에 있는 트리에 물이 채워지면 현재 자신이 위치한 트리의 높이만큼의 물이 채워지는 방식이다. 따라서, 해당 위치에 얼마나 물이 채워져있는지는 자기 자신을 루트 노트로 가지는 subtree안에 속한 구간할을 구하면 된다. 따라서 트리의 구간합을 구하는 방식이므로 오일러 투어 테크닉(ETT)를 생각해주면 된다. 따라서 노드 i안에 있는 물의 양은 다음과 같다. $$query[dfs\_in[i], dfs\_out[i]] * depth[i]$$ 이해가 안된다면 다음 블로그 글을 참고하도록 하자. https://thekeykim.github.io/posts/BOJ_18227/ [백준] 18227 - 성대나라의 물탱크 C++ 문제링크 18227 - 성대나라의 물탱크 문제 성대나라에는 각..

Approach 각 세그먼트의 노드에서 가장 최댓값, 그 다음 최댓값을 가지고 있으면 해당 쿼리에서의 최댓값과 그 다음 최댓값을 쉽게 도출할 수 있다. 다만, 2개의 value를 핸들링해야하는 상황이므로 pair도 뭐 가능하긴한데 class를 활용해주었다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class max_store{ public: int max_1; int max_2; max_store(){ max_1 = -1; max_2 = -1; } max_store(int a){ max_1 = a; max_2 = -1; } max_store(int a, int ..

Approach 특정 구간에서 k보다 작은 개수/큰 개수는 일반적으로 머지 소트 트리를 활용해서 처리하는 경우가 많다. 머지소트가 진행되는 양상을 잘 살펴보면, 세그먼트가 구성되는 느낌이랑 거의 유사하다. 따라서 어떠한 쿼리에서 k보다 큰 개수를 구하는 과정은 다음과 같다. 1) 원하는 쿼리와 현재 탐색중인 쿼리가 전혀 교차하지 않으면 0 2) 원하는 쿼리가 현재 탐색중인 쿼리를 포함하고 있을 경우, 이진탐색하여 k보다 큰 개수를 구한다. (upper bound) 3) 겹치는 경우에는 재귀적으로 처리하면 1)과 2)의 연산의 합으로 구할 수 있다. k보다 크거나 같은/ 작거나 같은/ 작은의 경우도 비슷한 방식으로 처리해주면 된다. Code #include #define fastio ios_base::sy..

Approach 문제 상황을 보면, 선택한 영화의 등수는 자신보다 더 앞에 놓여진 영화의 개수를 통해 구할 수 있다. 그런데 문제가 되는 상황이 영화를 뽑으면 위치가 가장 앞으로 된다는 것인데, 옮기는 횟수만큼의 추가적인 공간을 확보해주게 되면 원하는 값은 $query[1, x_i] - 1$로 구할 수 있게 된다. 즉, 세그 공간 자체를 $4 * (n + m)$만큼 잡아주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int seg[800000]; void update(int node_index, int node_left, int node_right, int..

Approach 문제를 잘 이해해보면, 현재 자신을 기준으로 자기보다 큰 숫자의 개수 + 1이 자기 등수이다. 이때, 큰 수부터 처리하면서 쿼리를 업데이트하면 이를 구간합으로 바꿔 이해할 수 있다. update하면서 해당 index가 속한 쿼리에 +1씩 시켜주면 된다. 또한, 실력 지표의 범위에 비해서 선수가 압도적으로 적기도 하고 해당 숫자가 너무 크다. 따라서 좌표 압축을 해서 seg의 크기를 줄이도록 하자. 만약 줄이지 해당 점수의 max의 4배를 해야하는데, 당연히 메모리 초과가 난다. 추가적으로 자신의 위치를 처리해야하므로 map을 통해 미리 저장해두도록 하자. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout..

Approach 문제를 잘 보면, cost를 결정하기 위해서는 궁극적으로 나무를 심는 위치를 기반으로 앞에 있는 나무의 개수와 어디에 위치해 있는지 판단하는 것이 중요하다. Let $i$번재 나무 위치를 $x_i$라 하자 그러면, $\text{Cost}_i = \sum\limits_{l \in [L, R], l \neq i} {|x_i - x_l|}$로 나타낼 수 있고, 고등학교 떄 학습한 것처럼 절댓값을 풀면 위 식은 $ \sum\limits_{l \in [L, x_i - 1]} {x_i - x_l} + \sum\limits_{l \in [x_i + 1, R]} {x_l - x_i}$로 나타낼 수 있다. 시그마를 처리해주면 $(n_{f} * x_i - S([L, x_i - 1])) + (S([x_i +..