블로그 옮겼습니다

문제 링크 \(1\le{N, M, K}\le{300,000}\)\(1\le{a_i, p_i}\le{10^9}\)M개의 구역이 있다. 각각의 구역은 N개의 국가중 하나에 의해 소유된다. N개의 국가는 각자 pi개의 운석 샘플을 가져가야 한다.유성이 K번 떨어진다. 유성이 한번 떨어질 때에는 특정 연속된 구간에 특정량이 떨어진다.li, ri, ai 로 표현될 수 있으며 구역은 원형이므로 li > ri 일 수도 있음에 유의한다. 유성이 어떤 국가에 속한 구역에 떨어지면 그 떨어진 개수만큼 해당 국가는 샘플을 습득할 수 있는 것이다.그렇다면 각 국가가 필요로 하는 샘플의 개수를 처음으로 충족하게 되는 건 몇 번째 유성이떨어졌을 때인지 구하는 문제이다. 즉, 답은 N개의 정수를 출력해야한다.naive 하게 생각해..

문제 링크 \(1\le{N, M}\le{10^5}\)\(0\le{Q}\le{10^5}\)이 문제는 N개의 노드가 있고, 각 노드는 M개의 그룹중 하나에 속한다. 그리고 총 Q개의 간선을 설치할건데1번부터 순차적으로 설치할것이다. 그럴 때에 각 그룹에 대해 그룹에 속한 노드들이 모두 하나의 컴포넌트로연결되는 최소 간선 번호를 구하는것이다. 그러므로 최종적으로 M개의 정수를 출력하면된다.Q번 간선까지 설치했는데도 모든 그룹 노드들이 연결되지않는다면 -1을 출력, 그리고 하나도 간선을 설치하지않아도 모두 연결되면 0을 출력하면된다. 일단 0을 출력하는 경우는 그룹에 속한 노드가 딱 하나만있는 경우밖에 없다. 그러므로 이경우만 따로 처리해주면 될 것이다. 일단 naive 하게 생각해보자. M개의 그룹에 대해서 ..