시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 25 | 8 | 8 | 32.000% |
Azusa, the witch of the highlands, has discovered a garden full of weird trees! Therefore, together with her friend, Laika, she decided to spend some time there taking care of the garden.
The garden can be viewed as a sequence of $N$ trees, where the trees are indexed from $1$ to $N$. Each tree has a certain non-negative integer height. Azusa will then spend her time according to a schedule containing $Q$ entries, which can be of several types:
(Note that “between” is meant inclusively; e.g. $1$, $2$, $3$, $4$, $5$ are “between” $1$ and $5$.)
Azusa is curious what the results of the tree inspection phases will be, and wants to know them without having to go through the entire schedule. Can you help her?
The contestant must implement the following four functions:
void initialise (int N, int Q, int h []); void cut (int l, int r, int k); void magic (int i, int x); long long int inspect (int l, int r);
The function initialise
is given $N$ (the number of trees), $Q$ (the number of entries in the schedule), and an array $h$, where $h[i]$ is the height of tree $i$, for $1 ≤ i ≤ N$. This function is called by the committee’s code exactly once, before any of the other three functions are called. The cut
, magic
and inspect
functions represent tree cutting, magic and tree inspecting phases respectively, and are characterised by their respective parameters. The contestant’s implementation of the inspect
function must return the sum of the heights of the trees with indices between $l$ and $r$.
The contestant should not implement the main
function. This will be implemented in the committee’s grader.cpp
file; you will be given a sample grader.cpp
in the attachments. Our main
function will read $N$, $Q$, the sequence of $N$ initial heights, and the $Q$ schedule entries. The three types of schedule entries (cut(l, r, k)
, magic(i, x)
and inspect(l, r)
) are encoded as 1 l r k
, 2 i x
and 3 l r
respectively. This is the input format that will be used in the examples below.
Note that the contestant is allowed to use global variables, additional functions, methods and classes.
cut
, magic
and inspect
functions will be called exactly $Q$ times in total.번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $N ≤ 1\,000$, $Q ≤ 1\,000$, $k = 1$ |
2 | 8 | $N ≤ 80\,000$, $Q ≤ 80\,000$, $k = 1$ |
3 | 8 | $N ≤ 1\,000$, $Q ≤ 1\,000$, there are no |
4 | 19 | There are no |
5 | 10 | $l = 1$, $r = N$ |
6 | 21 | $N ≤ 80\,000$, $Q ≤ 80\,000$ |
7 | 29 | No further restrictions |
6 10 1 2 3 1 2 3 1 1 6 3 3 1 6 1 1 3 3 3 1 6 1 1 3 1000 3 1 6 2 1 1000 3 1 6 1 1 3 999 3 1 5
9 6 5 1005 4
In the first phase, after each of the $3$ days of tree cutting, the heights of the trees are $1, 2, 2, 1, 2, 3$; $1, 2, 2, 1, 2, 2$; and $1, 1, 2, 1, 2, 2$. The sum of these values is $9$, which is the answer to the inspection in the second phase.
In the third phase, after each of the $3$ days of tree cutting, the heights of the trees are $1, 1, 1, 1, 2, 2$; $0, 1, 1, 1, 2, 2$; and $0, 0, 1, 1, 2, 2$. The sum of these values is $6$, which is the answer to the inspection in the fourth phase.
In the fifth phase, after each of the $1000$ days of tree cutting, the heights of the trees are $0, 0, 0, 1, 2, 2$. This is because a tree with height $0$ cannot be cut. The sum of these values is $5$, which is the answer to the inspection in the sixth phase.
In the seventh phase, the first tree is grown to height $1000$, giving us tree heights $1000, 0, 0, 1, 2, 2$. The sum of these values is $1005$, which is the answer to the inspection in the eighth phase.
In the ninth phase, each of the $999$ days of tree cutting reduces the height of the first tree by $1$. This gives us tree heights $1, 0, 0, 1, 2, 2$ at the end of the phase. The sum of the first five of these values is $4$, which is the answer to the inspection in the tenth and final phase.
C++17, C++20, C++17 (Clang), C++20 (Clang)