25020번 - 코딩 테스트 서브태스크언어 제한함수 구현

회사는 요즘 늘어난 코딩 테스트의 인기에 힘입어 코딩 테스트용 문제를 만들어 IT 기업에 판매하는 일을 하고 있다.

회사는 편의를 위해 만든 문제의 난이도를 $0$단계에서 $N-1$단계로 나눴다. 현재 회사에는 난이도가 $i$단계로 평가된 문제가 $A[i]$개 준비되어 있고, 난이도 매기기가 애매해서 $i$단계 혹은 $i+1$단계로 평가된 문제도 $B[i]$개 준비되어 있다. 이외의 방식으로 난이도가 평가된 문제는 없다.

회사는 지금 문제를 판매할 기업을 물색하고 있다. 현재 구매 의향을 나타낸 기업은 총 $M$곳이 있으며, $0$부터 $M-1$까지의 번호가 붙어 있다. $j$ ($0 \le j \le M-1$)번 기업은 회사의 문제들 중 난이도가 $L[j]$단계 이상이고 $U[j]$단계 이하인 문제에만 관심이 있다.

회사는 $j$번 기업에게 문제를 판매할 때 $L[j]$단계에서 $U[j]$단계의 문제를 난이도 별로 하나씩 뽑아 묶음으로 판매하려고 한다. 이를 하나의 세트라고 하자.

$j$번 기업에게만 문제를 판매한다면 최대 몇 개의 세트를 판매할 수 있을까? 

난이도가 $i$단계 혹은 $i+1$단계로 평가된 문제는 난이도를 둘 증 하나로 적절히 설정해서 판매하는 세트 개수가 최대한 많아지도록 해야 하며, 판매하는 모든 세트에 걸쳐 같은 문제가 여러 번 들어기지 않도록 해야 한다.

여러분은 아래 함수를 구현해야 한다.

vector<int> testset(vector<int> A, vector<int> B, vector<int> L, vector<int> U)

• 이 함수는 단 한 번만 호출된다.
• $A$: 길이가 $N$인 정수 배열. 모든 $i$ $(0 \le i \le N - 1)$에 대해, $A[i]$는 난이도가 $i$단계로 평가된 문제의 개수이다. 
• $B$: 길이가 $N-1$인 정수 배열. 모든 $i$ $(0 \le i \le N - 2)$에 대해, $B[i]$는 난이도가 $i$단계 혹은 $i+1$단계로 평가된 문제의 개수이다.
• $L$, $U$: 길이가 $M$인 정수 배열. 모든 $j$ $(0 \le j \le M - 1)$에 대해,  $L[j]$, $U[j]$는 각각 $j$번 기업이 원하는 문제의 최소 난이도와 최대 난이도이다.
• 이 함수는 길이가 $M$인 정수 배열 $S$를 반환해야 한다. 모든 $j$ $(0 \le j \le M - 1)$에 대해,  $S[j]$는 $j$번 기업에게 판매 가능한 $L[j]$단계에서 $U[j]$단계의 문제로 이루어진 세트의 최대 개수이다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

$N = 4$, $M = 2$, $A = [2, 3, 1, 1]$, $B = [1, 3, 2]$, $L = [0, 1]$, $U = [3, 2]$ 인 경우를 생각해 보자. 

그레이더는 다음과 같이 함수를 호출한다.

testset({2, 3, 1, 1}, {1, 3, 2}, {0, 1}, {3, 2})

0번 기업은 난이도가 0단계 이상, 3단계 이하인 문제를 원한다. 다음과 같은 방식으로 3개의 세트를 만들 수 있으며, 난이도가 1단계인 문제 하나만 남아 더 이상의 세트를 만드는 것은 불가능하다.

1번 기업은 난이도가 1단계 이상, 2단계 이하인 문제를 원한다. 다음과 같은 방식으로 5개의 세트를 만들 수 있으며, 가능한 모든 문제를 사용해 더 이상의 세트를 만드는 것은 불가능하다.

그러므로, 호출된 testset 함수는 $S=[3, 5]$를 반환해야 한다.

• $2 \le N \le 100\,000 $
• $1 \le M \le 100\,000 $
• $0 \le A[i] \le 10^8 $ (모든 $0 \le i \le N-1$)
• $0 \le B[i] \le 10^8 $ (모든 $0 \le i \le N-2$)
• $0 \le L[i] \le U[i] \le N-1 $ (모든 $0 \le j \le M-1$)

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line 1: $N$ $M$
• Line 2: $A[0]$ $A[1]$ $\cdots$ $A[N-1]$
• Line 3: $B[0]$ $B[1]$ $\cdots$ $B[N-2]$
• Line $4 + j$ $(0 \le j \le M-1)$: $L[j]$ $U[j]$

Sample grader의 출력 형식은 아래와 같다.

• Line $1 + j$ $(0 \le j \le M-1)$: $S[j]$

• codingtest_public.zip