유성우와 영지 수확
다이아몬드 III의견: 0
원형으로 배치된 \(S\)개의 구역이 번호 \(1\)부터 \(S\)까지 시계 방향으로 놓여 있다. 각 구역은 정확히 한 영주의 소유이며, 영주는 \(1\)번부터 \(N\)번까지 있고 모든 영주는 최소 하나의 구역을 가진다. 영주 \(k\)는 목표량 \(w_k\)를 채우려 한다.
총 \(Q\)번의 유성우가 내린다. \(t\)번째 유성우는 원형 구간 \([l, r]\) (즉 \(l\)부터 \(r\)까지 시계 방향, \(l>r\)이면 \(S\)를 지나 한 바퀴 돌아감)에 속한 모든 구역에 각각 \(a\)만큼을 떨어뜨린다. 유성우는 누적된다.
각 영주에 대해, 자신이 소유한 구역들에 쌓인 운석의 총량이 처음으로 목표량 \(w_k\) 이상이 되는 유성우의 번호 \(t\)를 구하여라. \(Q\)번 안에 목표를 못 채우면 NIE를 출력한다.
영주마다 따로 이분 탐색하면 너무 느리다.
\(1 \le N \le S \le 300{,}000\)
\(1 \le Q \le 300{,}000\)
\(1 \le w_k \le 10^9\)
\(1 \le l, r \le S\), \(1 \le a \le 10^9\)
첫 줄에 구역 수 \(S\)와 영주 수 \(N\)이 주어진다.
둘째 줄에 \(S\)개의 정수가 주어지며 \(i\)번째 값은 구역 \(i\)를 소유한 영주의 번호이다.
셋째 줄에 \(N\)개의 정수 \(w_1, \dots, w_N\)이 주어진다.
넷째 줄에 유성우 수 \(Q\)가 주어진다.
다음 \(Q\)개의 줄에 각 유성우의 \(l\), \(r\), \(a\)가 주어진다.
각 영주 \(1\)부터 \(N\)까지에 대해 답을 한 줄에 하나씩 출력한다.
5 3
1 2 3 1 2
5 6 7
3
1 3 1
2 4 2
1 5 1
3
NIE
NIE구역 소유: 1,2,3,1,2. 유성우1은 [1,3]에 1, 유성우2는 [2,4]에 2, 유성우3은 [1,5]에 1. 각 영주가 목표를 처음 채우는 유성우 번호를 출력한다.
3 3
1 2 3
100 1 1
2
1 3 1
2 2 1
NIE
1
1영주1의 목표 100은 두 번의 유성우로 채울 수 없어 NIE. 영주2,3은 첫 유성우로 목표 1 달성.
riseoj 작성
출처 Original
평가 및 의견
유성우와 영지 수확
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
유성우와 영지 수확