34352번 - Lottery 서브태스크다국어언어 제한함수 구현

문제

JOI-kun is planning a lottery event. In this lottery event, an even number of bags will be used. Each bag initially contains some red balls and blue balls (possibly zero). Participants will keep coming to the lottery event until at least one of the bags becomes empty. Each participant draws one ball from each bag. If the total number of red and blue balls they have drawn ends up being equal, they receive one prize. Balls drawn are not returned to the bags.

As preparation, JOI-kun has prepared $N$ bags, numbered from 0ドル$ to $N − 1$. Bag $i$ (0ドル ≤ i ≤ N − 1$) contains $X_i$ red balls and $Y_i$ blue balls.

In the lottery event, some of the $N$ bags will be selected for use. There are $Q$ plans for selecting bags. In the $j$-th plan (1ドル ≤ j ≤ Q$), the bags $L_j , L_{j + 1}, \dots , R_j$ are used. Here, $R_j − L_j + 1$ is even.

To prepare the prizes for the event, JOI-kun wants to know, for each plan, the maximum possible total number of prizes participants can obtain. Write a program that, given the bag contents and the plans, returns the maximum possible total number of prizes participants can obtain for each plan.

구현 상세

You need to submit one file.

The file is lottery.cpp. The program should include lottery.h using the preprocessing directive #include.

In lottery.cpp, the following functions should be implemented.

void init(int N, int Q, std::vector<int> X, std::vector<int> Y)

• This function is called only once, at the beginning.
• The parameter N is the number of bags $N$ prepared by JOI-kun.
• The parameter Q is the number of plans $Q$ for selecting bags.
• The parameter X is an array of length $N$. X[i] (0ドル ≤ i ≤ N − 1$) is the number of red balls in bag $i$.
• The parameter Y is an array of length $N$. Y[i] (0ドル ≤ i ≤ N − 1$) is the number of blue balls in bag $i$.

int max_prize(int L, int R)

• This function is called $Q$ times after the function init is called.
• On the $j$-th call (1ドル ≤ j ≤ Q$) of this function:
  • The parameter L is the value $L_j$ of the $j$-th plan.
  • The parameter R is the value $R_j$ of the $j$-th plan.
  • This function must return the maximum possible total number of prizes participants can obtain in the $j$-th plan.

Important Notices

• Your program can implement other functions for internal use, or use global variables.
• Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

컴파일과 테스트 실행

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp. To test your program, place the files grader.cpp, lottery.cpp, and lottery.h in the same directory, and compile them using the following command:

g++ -std=gnu++20 -O2 -o grader grader.cpp lottery.cpp

Alternatively, you can execute the compile.sh file included in the archive by running:

./compile.sh

If the compilation is successful, an executable file named grader will be generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

Input for the Sample Grader

The sample grader reads input from standard input in the following format:

$N$ $Q$

$X_0$ $X_1$ $\cdots$ $X_{N−1}$

$Y_0$ $Y_1$ $\cdots$ $Y_{N−1}$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_Q$ $R_Q$

Output of the Sample Grader

The sample grader outputs the return value of function max_prize in one line to the standard output, after every call of this function.

입력

출력

제한

• 2ドル ≤ N ≤ 200,円 000$.
• 1ドル ≤ Q ≤ 500,円 000$.
• 0ドル ≤ X_i ≤ 10^9$ (0ドル ≤ i ≤ N − 1$).
• 0ドル ≤ Y_i ≤ 10^9$ (0ドル ≤ i ≤ N − 1$).
• 0ドル ≤ L_j < R_j ≤ N − 1$ (1ドル ≤ j ≤ Q$).
• $R_j − L_j + 1$ is even (1ドル ≤ j ≤ Q$).
• Given values are all integers.

서브태스크

힌트

첨부

• 2025-open-lottery-dist.zip