문제 링크 http://icpc.me/7626 풀이 백준[3392] 화성지도 이 문제와 거의 유사하다. 위 문제와 풀이는 모두 동일한데 값의 범위가 매우 크기 때문에 좌표압축을 해야한다. 코드 #include #include #include using namespace std; using ll = long long; using pll = pair; const ll MAX = 4e5 + 5; struct T { T(ll x, pll y, ll finish) : x(x), y(y), finish(finish) {} ll x; pll y; ll finish; }; vector v; vector ySet; ll seg[MAX * 4]; ll cnt[MAX * 4]; void update(ll node, ll s..

문제 링크 http://icpc.me/3392 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. 모든 점을 x축 기준으로 정렬을 하여 왼쪽부터 쓸면서 값을 구하면 된다. 이때 세그먼트 트리로 y축의 점들을 저장해놓는다. 만약 점이 시작하는 점이라면 세그먼트 트리에 1을 더하고, 끝나는 점이라면 -1을 더하면 된다. 하지만 겹치는 부분의 넓이는 구하면 안되기 때문에 위처럼 저장하여 넓이를 바로 계산하면 문제가 발생한다. 그렇기 때문에 세그먼트 트리를 2개 활용한다. 하나는 구간에 점이 몇개가 있는지를 저장하고, 하나는 점이 있는지 유무만 확인할 수 있게 저장한다. 코드 #include #include using namespace std; using pii = pair; struct T { T(int..

문제 링크 http://icpc.me/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 풀이 스위핑을 이용하여 풀이할 수 있다. a에서 태워 b에서 내려준다고 할 때, 상근이가 무조건 M에 도달해야 하기 때문에 a b인 상황에서 언제 되돌아가서 내려줄건지 고려를 잘해야 한다. 최단 경로로 가기 위해서는 같은 경로를 여러 번 돌아가면 안 된다. 그렇기 때문에 a -> b와 c -> d로 가는 두 경로가 만약 겹친다면 한 번에 움직여야 한다. 코드 ..

문제 링크 http://icpc.me/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 풀이 스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다. y좌표를 좌표압축을 한 후에 x좌표 기준 오름차순 정렬하고 만약 x좌표가 같다면 y좌표가 큰 순으로 정렬한다. k번째 점과 쌍이 될 수 있는 점의 수는 x좌표가 k보다 작고, y좌표는 k보다 크거나 같은 점의 수이다. 이때 이 점들을 전탐색하면 O(N^2)으로 시간이 터져버린다. 그렇기 때문에 k번째 점과 쌍이 될 수 있는 점의 수를 세그먼트 트리를 이용하여 시간을 줄여줘야 한다. k의 y좌표 ~ 범위 끝까지의 수를 가져오면 빠르게 수를 구할 수 있다. 세그먼트 트리를 ..

문제 링크 http://icpc.me/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이 스위핑 알고리즘을 이용하여 풀이 할 수 있다. 여기에 다른분이 잘 정리 해놨다. 수를 x좌표 기준으로 오름차순으로 정렬한 후 범위가 겹친다면 범위를 점차 늘려나가고, 겹치지 않을 때 그동안 늘려온 범위의 값을 더하며 새로운 범위를 시작한다. 코드 #include #include using namespace std; using pii = pair; pii arr[1000006]; in..