Submit solution

Points:
10 (partial)

Time limit:
1.4s

Memory limit:
256M

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, ~~CommonLisp~~, D, Dart, F#, Forth, Fortran, Go, ~~Groovy~~, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ~~Nim~~, ~~ObjC~~, OCaml, ~~Octave~~, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 v`

Change the -th of the array to .`S l r`

Output the sum of all the elements from the -th to the -th index, inclusive.`Q v`

Output 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?

#### Input Specification

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.

#### Output Specification

For each `S`

or `Q`

operation, output the answer on its own line. Note that you may need to use 64-bit integers to store the answer.

#### Sample Input

```
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
```

#### Sample Output

```
8
12
21
12
7
9
6
```

## Comments

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.

Change

`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?

TLEI 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.

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

cout << endl;

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.