I’m having a hard time understanding what is the problem asking since the wording is really confusing. So I wonder if anyone could walk me through the example test case? Please note that, I’m not asking for hints, my goal is just to clarify the problem.
Here is the original question:
what is the count of the indices i
(1 ≤ i ≤ m), that all balloons in the
boxes with the indices from l[i] to
r[i] are already bursted.
- Does “count” means the number of indices from 1 to m?
- Does “all ballon” means all the balloons must be busted within range [l[i], r[i]]?
Here is another one:
The next k line contains integers
x[1], x[2], …, x[k]. Index of the
box, in what Sereja bursted a balloon
at the step number i (1 ≤ i ≤ k), is
denoted as y[i]., which can be found
as: y[i] = x[i] + ans[i - 1], wherein
ans[0] = 0, аnd ans[i] (i>0) — is the
answer on the problem after ith
bursting of the balloons.
- Are x[1], x[2], …, x[k] indices of box? Then what is y[i]?
Now let’s take a look at the test case:
Input:
5 3
1 1 1 1 1
5 5
2 2
1 3
5
4
2
0
2
3
Output:
0
1
1
2
3
So we have 5 boxes (namely 1 to 5, index: 0 to 4), and 3 ranges: (5,5), (2,2) and (1,3)
At the beginning, all the balloons are not yet burst.
1 1 1 1 1
Now Sereja perform busting in k = 5 steps:
Step 1: 4
1 1 1 1 0
Step 2: 2
1 1 0 1 0
Step 3: 0
0 1 0 1 0
Step 4: 2
0 1 0 1 0
Step 5: 3
0 1 0 0 0
This is what I understand by “burst” a balloon at each step, then how come the answer is
0
1
1
2
3
