All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Lira loves marbles very much and she especially loves to play with them with her school friends.
Today, Lira is very excited, as her mom said she would give her and her friends some new marbles for her to play with. She immediately requested her mom to give her the new marbles, but, her mom had some tricks kept up her sleeve:
Mom: "Not so fast, young girl!! These won't come for free! If you want to keep playing with them, you must prove you deserve them!!"
Lira: *moans* "Alright, mom, what do I have to do now?"
(Yes, Lira's mom can be quite annoying)
Mom: "Well, you can assume that I have an array A of size N , where N is the total number of students I will give marbles to, and A[i] is the number of marbles each student initially has."
Lira: *smiles slightly* "So you're feeling generous hum?"
Mom: "Well, not too generous... imagine I wanted to give more marbles to some of your school friends who do well on their exams, or, on the other hand take away some marbles from the greedier friends."
Lira: "Mom, c'mon that's too easy!!"
Mom: "Alright, so given a group of students, starting on student i and ending on student j, I want to know how many marbles they have together!"
Well, it turns out that Lira actually did solve this problem and she did it very efficiently!!
It's now your turn to solve the problem that Lira already did in a brilliant way!
Lira is given array A, which contains elements between 1000 and 2000.
Three types of queries can be performed on this array: add a given value to a single element on it, subtract a given value from a single element on it and find the sum of the values between indexes i and j, i.e. A[i]+...+A[j]. Check input and example section for details.
The first line of the input contains two integers: N and Q, denoting respectively, the number of students that there are present to receive the marbles as a gift and the number of actions Lira's mom will perform.
These actions can be of three different types:
The output should contain as many lines as the number of queries S and it should contain the answer for each query on a separate line
- 2 ≤ N ≤ 1000000
- 3 ≤ Q ≤ 50000
- The array is 0-indexed.
- 1000 ≤ A[i] ≤ 2000
- A student can never have a negative value of marbles. (i.e. there's no data which can cause a student to have a negative value of marbles)
- 0 ≤ i, j ≤ N-1, and i ≤ j for the sum query
- At any given time, it is assured that the maximum number of marbles each student can have (num_marbles) never exceeds the size of the int data type.
5 3 1000 1002 1003 1004 1005 S 0 2 G 0 3 S 0 2 Output: 3005 3008
|Tags||dec13, easy, kuruma|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.