Points: 10 (partial)
Time limit: 1.4s
Memory limit: 256M
is doing a contest. He comes across the following problem:
You have an array of elements, indexed from to . There are operations you need to perform on it.
Each operation is one of the following:
C x vChange the -th element of the array to .
S l rOutput the sum of all the elements from the -th to the -th index, inclusive.
Q vOutput how many elements are less than or equal to in the array.
At any time, every element in the array is between and (inclusive).
knows that one fast solution uses a Binary Indexed Tree. He practices that data structure every day, but still somehow manages to get it wrong. Will you show him a working example?
The first line has and .
The second line has integers, the original array.
The next lines each contain an operation in the format described above.
Q operation, output the answer on its own line. Note that you may need to use 64-bit integers to store the answer.
10 10 4 8 4 5 6 3 2 2 8 1 C 7 6 Q 7 S 2 3 S 1 4 C 4 9 S 2 3 Q 6 C 3 9 S 6 7 Q 6
8 12 21 12 7 9 6
Someone should have told me that the largest element in the array is at most 100000, would have saved a lot of time implementing an order statistic tree.
It says in the problem statement.
Can someone take a look at my code, I am wrong answering on the first three cases and I don't know what the problem is.
while(value <= N)to
while(value <= maxvalue).
Makes sense, thank you.
Is this talking about the test cases themselves or something that needs to be factored in the solution?
I know my solution is O(Mlog(N)), but it still seems I am TLEing. Could someone please tell me why this is happening? Thank you!
Edit: Turns out upper_bound and lower_bound are slow.
I'm just wondering, is my algorithm for solving the question wrong? I'm TLEing on 3 test cases, but I can't seem to figure out what's causing the problem.
It also happen to me
get rid of your exception checking cases.
I changed the exceptions to if and else statements, but it didn't change much.
EDIT: calculating values beforehand is always a good idea...
I submit the exact same code, but only one TLE's on cases...
Flushing output is not guaranteed to be a constant time on every judge.
I'm not sure what you mean? Does that mean my code is technically correct time-wise or?
Flushing means using
kobortor u snake going to level 3 on the same day i went to lvl 2 ;(
And the same day you went to lvl 2 awaykened and jefferyxiao went to lvl 4.
and the day before fataleagle went to lvl5 ;(
To be honest Fataleagle is just straight up OP.