https://www.acmicpc.net/problem/8201 8201번: Pilots In the first line of the standard input two integers are given, t and n (0 ≤ t ≤ 2,000,000,000, 1 ≤ n ≤ 3,000,000), separated by a single space, denoting the tolerance level and the number of yoke's position measurements taken. The second line give www.acmicpc.net 구간의 최댓값을 저장하는 세그먼트 트리와, 구간의 최솟값을 저장하는 세그먼트를 만들고, 구간의 최댓값과 최솟값을 동시에 반환하는 세그먼트 트리의 쿼..

https://www.acmicpc.net/problem/20930 20930번: 우주 정거장 첫 번째 줄에는 우주 정거장 개수 $N$과 질문의 개수 $Q$가 주어진다. ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$) 다음 $N$개의 줄에는 $i$번 우주 정거장의 양 끝점을 나타내는 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$ www.acmicpc.net 선분에 대한 정보를 x좌표에 대한 정보, y좌표에 대한 정보를 나누어서 정렬한 뒤 인접한 선분들과 이동할 수 있으면 유니온 파인드의 유니온을 하는 방법을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, q; ..

https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 시작 지점의 좌표가 (500, 500)인 위치에서 시작하는 좌표로 만들었다. 또한 위치마다 {왼쪽 위, 오른쪽 위, 아래}로 갈 수 있는 위치와 {위, 왼쪽 아래, 오른쪽 아래}로 갈 수 있는 위치로 나누어졌다는 것을 고려하였고, 직전 위치로 이동하지 않기 위해 직전에 어디서 왔는지도 고려했다. 방문한 위치에 왔을때 회전을 n번 했는지 확인하고, 방문하지 않은 위치인데 회전을 n번 했..

https://www.acmicpc.net/problem/1321 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 부대 인원에 대한 세그먼트 트리를 만들고 1번 부대부터 mid번 부대까지 인원이 몇 명인지 구하는 이분 탐색을 통해 문제를 해결했다. 코드 #include #include #include using namespace std; int n; int m; vector people(500001, 0); vector sgmtt(500001 * 4, 0); int MakeSgmtt(int he..

https://www.acmicpc.net/problem/2532 2532번: 먹이사슬 1부터 N까지 번호가 붙여져 있는 N마리 서로 다른 동물이 있다. 모든 동물은 동일한 하나의 수평선 상에서 연속된 구간 내에서 활동한다. 이 구간을 그 동물의 활동영역이라 한다. 동물의 활동영 www.acmicpc.net 정렬 뒤 range.erase(unique(range.begin(), range.end()), range.end())를 통해 중복된 값들을 지우고 왼쪽 범위가 작은 게 앞, 왼쪽 범위가 같다면 오른쪽 범위가 큰 게 앞에 오도록 정렬을 하고, 끝부터 확인해서 오른쪽 범위의 가장 긴 증가하는 부분 수열(n log n)을 찾는 방법으로 문제를 해결했다. 이때 upper_bound로 해서 같은 값이 chec..

https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 위상 정렬을 이용하여 들어오는 강 중에서 순서가 큰 값을 찾았을 때, 기존 큰 값과 같은 값일 때를 고려하였고 큐에 들어갈 때 가장 큰 값이 두 개 이상인 경우도 고려하여 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int tc; int k, m, p; vector adj[1001]; vector ..