#PQJ1941x10185. QOJ 1941_10185

    ID: 2761 传统题 10000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2025 集训线段树单调栈

QOJ 1941_10185

2025 국제정보올림피아드국가대표2차선발고사(2025. 02. 22.) 뗏목제작(raft) 울창한두숲KOI 숲과IOI 숲에는많은나무들이우거져있다. KOI 숲에는0번부터N −1번까지, 총 N개의나무가왼쪽에서오른쪽으로일렬로줄지어있으며, IOI 숲에는0번부터M −1번까지총M개의 나무가같은방식으로일렬로줄지어있다. KOI 숲의i (0 ≤i ≤N −1)번나무의높이는A[i], IOI 숲의j (0 ≤j ≤M −1)번나무의높이는B[j]이다. 당신의부족은외딴섬에서바다의신께기도를드리는오랜전통을가지고있으며, 그의식을치르기위해 뗏목을만들어야한다. 당신은두숲에서나무를벌목하여뗏목을제작하기로하였다. 뗏목을타고섬까지가는것은매우위험하기때문에, 당신은뗏목을최대한안정적으로만들고자한다. 뗏목은나무들을옆으로이어붙여만들며, 그안에포함되는직사각형모양의면적이클수록안정적이다. 구체적으로, 뗏목을구성하는나무의높이가왼쪽에서부터H[0], H[1], . . . , H[L −1]이라고할때, 뗏목의 안정성은 �  max min(H[s], . . . , H[l]) × (l −s + 1) 0≤s≤l≤L−1 의값으로정의된다. 즉, 가능한모든연속된구간[s, l]에대해그구간에포함되는나무들의최소높이를 구하고, 그높이에구간너비인(l −s + 1)를곱했을때의최댓값을의미한다. 부족의전통에따라, 뗏목을구성하는나무들은다음과같은규칙을따라야한다.

  1. 벌목한나무는모두뗏목에사용해야한다.
  2. KOI 숲에서잘라온나무들은원래숲내에서의순서를유지해야한다. 즉, 원래숲에서나무X가나무 Y 보다왼쪽에있었다면, 뗏목에서도X가Y 보다왼쪽에있어야한다.
  3. IOI 숲에서잘라온나무들도마찬가지로원래순서를유지해야한다. KOI 숲의나무들은0번부터N −1번까지N그루모두를모두벌목하기로결정되었다. 그러나, IOI 숲에서어떤나무들을벌목할지는아직결정되지않았다. 당신은0부터Q −1 까지번호붙여진Q개질의에 답해야한다. 질의들은길이Q의배열L과R로표현된다. 질의k(0 ≤k ≤Q −1)의답은IOI 숲에서번호가 L[k] 이상R[k] 이하인나무들을벌목하는경우얻을수있는뗏목의가능한최대안정성이다. 함수목록및정의 여러분은아래함수를구현해야한다. std::vector max_stability(std::vector A, std::vector B, std::vector L, std::vector R) • A: 크기가N인정수배열 • B: 크기가M인정수배열 • L, R: 크기가Q인정수배열 • 이함수는크기가Q인정수배열을반환한다. Page 1 of 5 2025 국제정보올림피아드국가대표2차선발고사(2025. 02. 22.) • 반환되는정수배열을C라할때, 0 이상Q−1 이하의정수k에대해C[k]는KOI 숲의모든나무와IOI 숲의번호가L[k] 이상R[k] 이하인나무들을벌목하는경우에뗏목의가능한최대안정성을나타내는 정수이다. • 이함수는매테스트케이스마다단한번호출된다. 제출하는소스코드의어느부분에서도입출력함수를실행해서는안된다. Page 2 of 5 2025 국제정보올림피아드국가대표2차선발고사(2025. 02. 22.) 제약조건 • 1 ≤N, M ≤150 000 • 1 ≤Q ≤500 000 • 모든0 ≤i ≤N −1 에대해1 ≤A[i] ≤109 • 모든0 ≤j ≤M −1 에대해1 ≤B[j] ≤109 • 모든0 ≤k ≤Q −1 에대해0 ≤L[k] ≤R[k] ≤M −1 부분문제
  4. (10점) • N, M, Q ≤3 000
  5. (8점) • Q ≤300
  6. (20점) • 모든0 ≤k ≤Q −1에대해다음두조건이성립한다. – L[k] = 0 또는B[L[k] −1] < min(B[L[k]], B[L[k] + 1], . . . , B[R[k]]) – R[k] = M −1 또는B[R[k] + 1] < min(B[L[k]], B[L[k] + 1], . . . , B[R[k]])
  7. (6점) • 모든0 ≤i ≤N −1에대해A[i] ≤50 • 모든0 ≤j ≤M −1에대해B[j] ≤50
  8. (14점) • 모든0 ≤i ≤N −1에대해A[i]가일정하다.
  9. (11점) • 모든0 ≤j ≤M −2에대해B[j] ≥B[j + 1]
  10. (13점) • 모든0 ≤k ≤Q −1에대해L[k] = 0
  11. (7점) • 모든0 ≤k ≤Q −1에대해R[k] −L[k]이동일하다.
  12. (11점) • 추가적인제약조건이없다. Page 3 of 5 2025 국제정보올림피아드국가대표2차선발고사(2025. 02. 22.) 예제1 N = 5, M = 4, Q = 2, A = [3, 3, 1, 6, 1], B = [3, 5, 7, 6], L = [0, 0], R = [1, 3]인경우를생각해보자. 그레이더는다음과같이함수를호출한다. max_stability([3, 3, 1, 6, 1], [3, 5, 7, 6], [0, 0], [1, 3]) L[0] = 0, R[0] = 1인경우뗏목의최대안정성은12이다. 12의안정성을얻는방법중하나는다음과같다: • 뗏목의왼쪽부터KOI 숲의0, 1번나무, IOI 숲의0, 1번나무, KOI 숲의2, 3, 4번나무순서 로구성한다. 이때뗏목을이루는나무들의높이는왼쪽부터H [3, 3, 3, 5, 1, 6, 1]이된다. = min(H[0], H[1], H[2], H[3]) = 3이므로3 × 4 = 12의안정성을가진다. L[0] = 0, R[0] = 3인경우뗏목의최대안정성은20이다. 20의안정성을얻는방법중하나는다음과같다: • 뗏목의왼쪽부터KOI 숲의0, 1, 2번나무, IOI 숲의0, 1, 2, 3번나무, KOI 숲의3, 4번나무순서 로구성한단. 이때뗏목을이루는나무들의높이는왼쪽부터H = [3, 3, 1, 3, 5, 7, 6, 6, 1]이된다. min(H[4], H[5], H[6], H[7]) = 5이므로5 × 4 = 20의안정성을가진다. 따라서함수는[12, 20]를반환하여야한다. 예제2 그레이더는다음과같이함수를호출한다. max_stability([9, 9, 9, 9, 9], [1, 2, 3, 4, 5, 6, 7, 8], [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7]) 함수는[45, 45, 45, 45, 45, 45, 45, 49]을반환하여야한다. 예제3 그레이더는다음과같이함수를호출한다. max_stability([1000000000, 1000000000, 1000000000], [1000000000, 1000000000], [0], [1]) 함수는[5000000000]을반환하여야한다. Sample grader Sample grader는아래와같은형식으로입력을받는다. • Line 1: N M Q • Line 2: A[0] A[1] . . . A[N −1] • Line 3: B[0] B[1] . . . B[M −1] • Line 4 + k (0 ≤k ≤Q −1): L[k] R[k] Page 4 of 5 2025 국제정보올림피아드국가대표2차선발고사(2025. 02. 22.) Sample grader는다음을출력한다. • Line 1 + k (0 ≤k ≤Q −1): max_stability가반환한정수배열을C라할때C[k]의값 Sample grader는실제채점에서사용하는그레이더와다를수있음에유의하라. Page 5 of 5