33609번 - 멋진 구간 서브태스크언어 제한함수 구현

지후는 정수로 이루어진 길이 $N$의 배열 $A$, $B$를 가지고 있다. 모든 정수 $0 \le i \le N-1$에 대해 $A[i] \le B[i]$를 만족한다.

다음 조건을 모두 만족하는 $[l, r]$을 멋진 구간이라고 정의한다:

• $l$, $r$은 정수
• $0 \le l \le r \le N-1$
• 다음 조건을 모두 만족하는 정수로 이루어진 길이 $N$의 배열 $C$가 존재한다:
  • 모든 정수 $0 \le i \le N-1$에 대해, $A[i] \le C[i] \le B[i]$
  • 모든 정수 $0 \le s \le e \le N-1$에 대해, $\sum_{i=l}^{r} C[i] \ge \sum_{i=s}^{e} C[i]$. 즉, $C[l \ldots r]$은 $C$의 최대 합 부분 배열(부분 배열 중 원소의 합이 가장 큰 부분 배열)이다.

지후는 멋진 구간이 얼마나 있는지 궁금해졌다.

구체적으로, 지후의 궁금증은 $0$부터 $Q-1$까지의 번호가 붙은 $Q$개의 질문으로 구성되어 있으며, 이는 정수로 이루어진 길이 $Q$의 배열 $L1$, $R1$, $L2$, $R2$로 표현된다.

$j$ ($0 \le j \le Q-1$)번 질문은 다음과 같다: $L1[j] \le l \le R1[j]$와 $L2[j] \le r \le R2[j]$를 모두 만족하는 멋진 구간 $[l, r]$은 몇 개인가?

여러분은 지후의 질문들에 답하는 프로그램을 작성해야 한다.

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

std::vector<long long> maxsum(std::vector<int> A, std::vector<int> B, std::vector<int> L1, std::vector<int> R1, std::vector<int> L2, std::vector<int> R2)

• $A$, $B$: 크기가 $N$인 정수 배열.
• $L1$, $R1$, $L2$, $R2$: 크기가 $Q$인 정수 배열.
• 이 함수는 크기가 $Q$인 정수 배열 $S$를 반환해야 한다. 모든 $j$ ($0 \le j \le Q-1$)에 대해, $S[j]$는 $j$번 질문에 대한 답이어야 한다.
• 이 함수는 단 한 번만 호출된다.

• $1 \le N, Q \le 250\,000$
• 모든 정수 $0 \le i \le N-1$에 대해 $-10^{9} \le A[i] \le B[i] \le 10^{9}$
• 모든 정수 $0 \le j \le Q-1$에 대해 $0 \le L1[j] \le R1[j] \le N-1$
• 모든 정수 $0 \le j \le Q-1$에 대해 $0 \le L2[j] \le R2[j] \le N-1$

• $1 \le N \le 500$

• $1 \le N \le 5\,000$

• $Q=1$
• $L1[0] = L2[0] = 0$
• $R1[0] = R2[0] = N-1$

• 모든 정수 $0 \le j \le Q-1$에 대해 $L1[j] = R1[j]$, $L2[j] = R2[j]$

• 추가적인 제약 조건이 없다.

$N=3$, $Q=3$, $A=[-1, -1, -1]$, $B=[2, -1, 2]$, $L1=[0, 0, 1]$, $R1=[2, 0, 2]$, $L2=[0, 0, 0]$, $R2=[2, 2, 1]$인 경우를 생각해 보자.

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

maxsum([-1, -1, -1], [2, -1, 2], [0, 0, 1], [2, 0, 2], [0, 0, 0], [2, 2, 1])

$[0, 0]$은 멋진 구간이다. $C = [1, -1, 0]$일 때, $C[0 \ldots 0]$이 $C$의 최대 합 부분 배열이기 때문이다.

$[0, 1]$은 멋진 구간이 아니다. $C[1]=-1$이므로, 어떤 $C$를 잡아도 $C[0] > C[0] + C[1]$이기 때문이다.

비슷한 방식으로 멋진 구간은 $[0, 0]$, $[0, 2]$, $[1, 1]$, $[2, 2]$ 밖에 없다는 것을 증명할 수 있다.

따라서, 함수는 $[4, 2, 1]$을 반환해야 한다.

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

• Line $1$: $N$ $Q$
• Line $2+i$ $(0 \le i \le N - 1)$: $A[i]$ $B[i]$
• Line $N+2+j$ $(0 \le j \le Q - 1)$: $L1[j]$ $R1[j]$ $L2[j]$ $R2[j]$

Sample grader는 다음을 출력한다.

• Line $1$: 함수 maxsum의 반환값을 $S$라 할 때, $S[0]$ $S[1]$ $\cdots$ $S[Q-1]$

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

• maxsum_public.zip