레야몬

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. 문제 성대 나라에는 각 도시별로 물탱크가 존재한다. 이 물탱크들은 모두 연결되어있으며 루트(수도)가 있는 트리의 형태를 가진다. A번 도시에 물을 채우면 수도에서부터 A번 도시까지 있는 경로에 수도부터 차례대로 1L, 2L, ..., (수도에서 A번까지의 도시 수)L 만큼 추가된다. 균관이는 어느 도시에 몇 리터의 물이 저장되어 있는지 알기 원한다. 균관이를 도와주는 프로그램을 작성하자. - 1 - 도시의 수 \((1 \leq N \leq 200,000)\), 수도 번호 \(C(1 \leq C \leq N)\) - N-1개 - 연결되어있는 두 도시의 번호쌍 x, y \((1 \leq x, y \leq N, x \neq y)\) - N+1 - 질의의 수 \(Q(1 \leq Q \leq 200,000)..

1. 문제 모든 판매원은 사수가 배정되며 한 회원당 단 한 명씩만 배정된다. 어떤 회원 A가 손해를 보면 그 회원의 모든 부사수도 같은 손해를 보고, 반대로 이익이 생기면 모든 부사수가 같은 이익을 본다. 승범이는 다음 두 종류의 명령을 처리하려 한다. 1 i w : 작은 i가 w만큼 이익/손해를 본다. 2 i : 직원 i의 현재 통장 잔액 출력 직원들은 빈 통장을 갖고 시작하며, 이익과 손해가 실시간으로 통장에 기록된다. 물론 통장 잔액은 음수일 수도 있다. -1- 판매원의 수 \(N(1 \leq N \leq 100,000)\), 명령의 수 \(M(1 \leq M \leq 100,000)\) 판매원들은 1~N번호로 매겨지며 승범이는 항상 1이다. -2- 1~N 사수가 순서대로 주어진다. 승범이는 사수가..

1. 문제 길이가 N인 수열 Ai가 주어진다. 이때, 아래 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai = v로 변경 k i j : k번째 1번 쿼리가 적용되었을 때 Ai, Ai+1, ..., Aj의 합을 출력 -1- 수열의 크기 \(N(1 \leq N \leq 100,000)\) -2- A1, A2, ..., AN \((1 \leq A_{i} \leq 1,000,000)\) -3- 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) -M줄- 쿼리가 한 줄에 하나씩 주어짐 \((1 \leq i \leq N, 1 \leq v \leq 1,000,000, 1 \leq i \leq j \leq N, 0 \leq k \leq (쿼리가 주어진 시점까지 있었던 1번 쿼리의 수)\) 모든 ..

13537번 수열과 쿼리 1과 문제가 비슷해서 함께 풀이됩니다. #include #include #include using namespace std; const int MAX_N = 100001; const int MAX_TR = 400001; // 수열의 크기 N과, 수열 A[i] int N; int A[MAX_N]; // 쿼리의 개수 M int M; // 찾으려는 값 k int k; // 머지 소트 트리 vector tr[MAX_TR]; // 머지 소트 트리 구현 void init(int s, int e, int no) { if(s==e) tr[no].push_back(A[s]); else { int m = (s+e)/2; init(s, m, no*2), init(m+1, e, no*2+1); tr[..

13544번과 문제가 비슷하여 함께 풀이됩니다. 1. 문제 길이가 N인 수열 Ai가 주어질 때 다음 쿼리를 수행하는 프로그램을 작성하시오. i, j, k : Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. -1- 수열의 크기 \(N(1 \leq N \leq 100,000)\) -2- Ai가 주어진다. \((1 \leq A_{i} \leq 10^{9})\) -3- 쿼리의 개수 \(M(1 \leq M \leq 100,000)\) -M개- 쿼리 i, j, k \((1 \leq i \leq j \leq N, 1 \leq k \leq 10^{9})\) 각각의 쿼리마다 한 줄에 하나씩 정답을 출력한다. 2. 재정의 \(A_{n}(i \leq n \leq j)\)수열 ..

거의 똑같은 문제인 10999번 구간 합 구하기 2와 함께 풀이됩니다. 1. 문제 어떤 N개의 수가 있다. 중간에 어떤 구간에 특정 수를 더해주는 과정이 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. -1- 수의 개수 \(N(1 \leq N \leq 1,000,000)\)과 \(M(1 \leq M \leq 10,000)\), \(K(1 \leq K \leq 10,000)\)이 주어진다. M은 수의 변경이 일어나는 횟수., K는 구간의 합을 구하는 횟수이다. -2~N+1- N개의 수가 주어진다. -N+2~N+M+K+1- 세 개의 정수 a, b, c 또는 a, b, c, d가 주어진다. a가 1인 경우 b~c번째 수에 d를 더하고, a가 2인 경우 b~c번째 수의 합을 출력하라. 입력으로 주어지는 모든..