레야몬

1. 문제 나라에는 1부터 N까지 번호가 매겨진 N개의 공항이 있고 M개의 시간 여행이 가능한 비행기가 있다. \((1 \leq N, M \leq 200,000)\). 비행기 \(j\)는 공항 \(c_j\) 시각 \(r_j\)에서 공항 \(d_j\) 시각 \(s_j\)에 착륙한다. \((0 \leq r_j, s_j \leq 10^9, s_j < r_j is possible)\). 게다가 공항에서 환승할 때는 \(a_i\)만큼의 시간이 걸린다. \((1 \leq a_i \leq 10^9)\). Bessie는 도시 1, 시각 0에서 시작할 때 1부터 N까지의 공항으로 각각 도착했을 때 최단 시각은 얼마인가? -1- N, M -M- \(c_j, r_j, d_j, s_j (1 \leq c_j, d_j \leq ..

1. 문제 N명의 학생은 3개의 시험을 치러 각 시험에서 같은 등수의 학생이 없도록 성적이 매겨졌다. A가 B보다 세 번의 시험에서 모두 성적이 좋으면 A가 '대단하다'라고 한다. 또, C라는 학생보다 '대단한' 학생이 없으면 C는 '굉장하다'라고 한다. '굉장한' 학생의 수를 구하시오 -1- \(N(1 \leq N \leq 500,000)\) -3- 각 시험에서 1등한 학생부터 N등한 학생이 순서대로 주어짐. 학생의 번호는 1번부터 N번까지 매겨져 있음. -1- '굉장한' 학생의 수 2. 재정의 3 과목 모두 자신보다 성적이 좋은 성적이 없는 사람의 수를 구하시오. 3. 실수한 점, 개선할 점 X 4. 해결 방법 3가지의 정렬을 이뤄내야 한다. 첫 번째 성적을 기준으로 먼저 정렬을 해보자. 첫 번째 성..

1. 문제 N개의 수가 있다. 이 때 다음 쿼리를 수행하라. 1 b c : b번째 수를 c로 바꾸기 2 b c : b부터 c까지의 곱을 구하여 출력하기 - 1 - : 수의 개수 \(N(1 \leq N \leq 1,000,000)\), 수의 변경이 일어나는 횟수 \(M(1 \leq M \leq 10,000)\), 구간의 곱을 구하는 횟수 \(K(1 \leq K \leq 10,000)\) - N개의 줄 - : N개의 숫자 - M+K개의 줄 - : a, b, c; K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다. 2. 재정의 유동적인 연속적인 수열의 곱을 계산하라 3. 해결 방법 세그먼트 트리 기본 문제 4. 실수한 점, 개선할 점 no와 start, end를 혼선하지 말기 첫..

1. 문제 함수 f:{1, 2, ..., m} -> {1, 2, ..., m} \(f_{1}(x) = f(x)\) \(f_{n+1}(x) = f(f_{n}(x))\) n, x가 주어질 때 \(f_{n}(x)\)를 계산하는 쿼리를 수행하시오 - 1 - \(m(1 \leq m \leq 200,000)\) - 2 - f(1), f(2), ..., f(m) - 3 - 쿼리의 개수 \(Q(1 \leq Q \leq 20,000)\) - Q개의 줄 - 정수 \(n, x(1 \leq n \leq 500,000, 1 \leq x \leq m)\) 주어지는 n, x마다 \(f_{n}(x)\) 출력 2. 재정의 X 3. 해결 방법 f[i][k] sparse array 4. 실수한 점, 개선할 점 input()을 안으로 뺐다..

1. 문제 N개의 중점으로 된 트리가 있다. 1~N번 매겨져 있고 간선은 1~N-1번 매겨져 있다. 아래 두 쿼리를 수행하는 프로그램을 작성하시오. 1 u v : u->v 경로 비용 출력 2 u v k : u->v 경로 정점 중 k번째 정점 출력 k는 u->v 경로에 포함된 정점 수보다 작다. - 1 - \(N(2 \leq N \leq 100,000)\) - N-1 개줄 - i번 간선 u->v와 비용 \(w(1 \leq w \leq 1,000,000)\) - N+1 - 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 쿼리 각 쿼리 결과 출력 2. 재정의 X 3. 해결 방법 트리 노드 차수 degree 설정 희소 배열 비용, 노드 메모 비용 : LCA 하면서 더하기 노드 ..

1. 문제 난이도 순서로 된 1~N번까지 총 N개의 문제로 되어 있는 문제를 풀려고 한다. 민오는 세 가지 조건에 따라 문제를 풀 순서를 정한다. N개의 문제를 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 푼다. 문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건에 맞는 민오가 풀 문제의 순서를 결정하시오. - 1 - 문제의 수 \(N(1 \leq N \leq 32,000)\), 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 \(M(1 \leq M \leq 100,000)\) - M개의 줄 - 두 정수의 순서쌍 A, B. A번 문제가 B번 문제보다 먼저 푸는 것이 좋다. 항상 문..

1. 문제 이 모듈은 사건 내에서 가능한 글자가 하나뿐이면 그 글자를 자동으로 입력한다. 모듈이 단어의 첫 글자를 추론하지 않는다. 사전의 모든 단어가 같은 알파벳으로 시작하더라도 반드시 첫 글자는 사용자가 버튼을 눌러 입력하여야 한다. 사건이 주어졌을 때, 이 모듈을 사용하면서 각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하시오. 여러 개의 테스트 케이스로 주어져 있다. - 1 - 단어의 개수 \(N(1 \leq N \leq 10^{5})\) - N개의 줄 - 1~80글자인 영어 소문자로만 이루어진 단어. 똑같은 단어가 2번 이상 주어지지 않는다. 각 테스트 케이스마다 주어진 단어의 길이의 총합은 최대 \(10^{6}\)이다. 각 테케마다 문제의 정답을 소수점 둘째 자리까지 반올림하여 ..

1. 문제 N개의 선분들이 2차원 평면상에 주어져 있다. 두 선분이 서로 만나는 경우에 두 선분은 같은 그룹에 속했다고 하며 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 이 N개의 선분들은 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속하는 선분의 개수는 몇 개인가? - 1 - \(N(1 \leq N \leq 3,000)\) - N개의 줄 - 선분의 양 끝점의 좌표 \(\left|x_{i} \right|, \left|y_{i} \right| \leq 5,000\) - 1 - 그룹의 수 - 2 - 가장 크기가 큰 그룹에 속한 선분의 개수 2. 재정의 선분 그룹 개수와 그 크기 구하기 3. 해결 방법 N*N = 9,000,000으로 CCW를 이용해 선분 교차를 모두 파악하고 이를 union..