JOI Spring Camp
-
JOI Spring Camp 2019 Day 1 SolutionsJOI Spring Camp 2020. 3. 18. 02:29
1. Examinations 학생별로 (S, T)가 입력으로 주어지는데, 이것을 쿼리와의 일관성을 위해(S, T, S+T)의 tuple로 해석하자. 쿼리 (X, Y, Z)가 들어오면, S>=X&&T>=Y&&S+T>=Z인 쌍의 개수를 출력하는 것이 문제이므로, 둘다 내림차순으로 적절히 정렬한 다음 2d update와 query로 문제를 풀어주자. 쿼리에 대한 분할정복+펜윅 스위핑을 하면 O((N+Q)log^2(N+Q))에 AC. 2. Naan 일단 각 사람별로 각각 한 조각에 sum/N씩 있도록 처음부터 잘라준다. 사람 i에 대한 j번째 조각의 끝점을 A[i][j]라 하겠다. A[i][j]는 유리수. (유리수끼리의 비교함수를 작성할때 overflow를 조심하도록 하자...) 이제 greedy하게 조각을 처..