목록구간 (2)
블로그 옮겼습니다
제5회 kriiicon 연습 세션 D번 구간들
https://oj.uz/problem/view/KRIII5P_3 \(1\leq{N}\leq{10^5},\,0\leq{s_{i},\,e_{i}}\leq{10^9}\)N개의 구간 \([s_{i},\,e_{i}]\) 가 입력으로 주어질 때(\(s_i\gt{e_i}\) 면 공집합)구간들의 교집합이란 \([max(s_1,\,s_2,\,\cdots,\,s_k),\,min(e_1,\,e_2,\,\cdots,\,e_k)]\)구간의 길이는 \(max(0,\,e_{i}-s_{i})\) 으로 정의 될 때선택된 구간들의 교집합의 길이가 1이상이도록 구간들을 선택할 때그 선택하는 방법의 수와 그 각각의 방법에서 교집합의 길이들의 합을 구하는 문제이다. 우선 방법의 수는 라인 스위핑으로도 풀 수 있고, 좌표압축+펜윅트리로도 풀..
Algorithm/Problem Solving
2017. 4. 30. 11:25
OJ.UZ) 초음속철도
https://oj.uz/problem/view/OJUZ11_rail 2
Algorithm/Problem Solving
2017. 2. 27. 10:21