CDC12_H - Halt The War


 

The war was terrible, thousands of humans and rainbow people lying down on the streets.
Ronny didn’t know what to do, so he decided to go and search for the Rainbowland Castle
and talk to the King. The rainbowlandians stared at Ronny with caution, waiting him to do
something bad just to get him and rainbow-kill him. Finally, Ronny made it to the King’s room
and talked to him about stopping this horrible war. The King accepted Ronny’s proposal, but
only with one condition, Ronny needed to prove once again what humanbeings were capable
of. The King said that if Ronny answered the Q queries that he had for him about an order
line of rainbow people numbered from 1 to N , he and his nation would go away. These rainbow
people had a letter with a number on it (Initially this number it’s 0).
There are two types of queries, modification queries and answer queries. The modification
queries consists on, given an interval from A to B inclusive ([A,B]), Ronny needed to update
those rainbow people’s letter, adding one to the number on it; so, by instance, if the interval is
[1,2], then Ronny needed to add one to the first and second rainbowlandian on the line. The
answer queries consists on, given an interval from A to B inclusive, Ronny should say the sum
of every rainbow people’s letter.
If Ronny can do this, the humans are saved! So he need your help, because he is not really that
good in maths and fast sums.
Input
The first line contains an integer T , which specifies the number of test cases. Then, will follow
the descriptions of T test cases.
For each test case you will get an integer N and an integer Q, that represents the number of
rainbowlandian in the line and the number of queries the King asks for. Then, Q lines will
follow, each containing a string and 2 integers, the type of query, that can be "modification"
or "answer" (Quotes for clarity), the first and the last rainbowlandian that Ronny must have
in mind in order to answer the query.
The input must be read from standard input.
Output
For each input case you must print the string "Scenario #i:" where i is the number of the
test case (Starting by 1), followed by Q lines with the answer of each query. If the query was
a modification query, then you should output "OK" (Quotes for clarity), otherwise, output the
CEIDEC 2012 - Contest Session
21
sum of the number from A to B inclusive.
The output must be written to standard output.

 

The war was terrible, thousands of humans and rainbow people lying down on the streets.

Ronny didn’t know what to do, so he decided to go and search for the Rainbowland Castle

and talk to the King. The rainbowlandians stared at Ronny with caution, waiting him to do

something bad just to get him and rainbow-kill him. Finally, Ronny made it to the King’s room

and talked to him about stopping this horrible war. The King accepted Ronny’s proposal, but

only with one condition, Ronny needed to prove once again what humanbeings were capable

of. The King said that if Ronny answered the Q queries that he had for him about an order

line of rainbow people numbered from 1 to N , he and his nation would go away. These rainbow

people had a letter with a number on it (Initially this number it’s 0).

There are two types of queries, modification queries and answer queries. The modification

queries consists on, given an interval from A to B inclusive ([A,B]), Ronny needed to update

those rainbow people’s letter, adding one to the number on it; so, by instance, if the interval is

[1,2], then Ronny needed to add one to the first and second rainbowlandian on the line. The

answer queries consists on, given an interval from A to B inclusive, Ronny should say the sum

of every rainbow people’s letter.

If Ronny can do this, the humans are saved! So he need your help, because he is not really that

good in maths and fast sums.

 

Input

The first line contains an integer T , which specifies the number of test cases. Then, will follow

the descriptions of T test cases.

For each test case you will get an integer N and an integer Q, that represents the number of

rainbowlandian in the line and the number of queries the King asks for. Then, Q lines will

follow, each containing a string and 2 integers, the type of query, that can be "modification"

or "answer" (Quotes for clarity), the first and the last rainbowlandian that Ronny must have

in mind in order to answer the query.

The input must be read from standard input.

 

Output

For each input case you must print the string "Scenario #i:" where i is the number of the

test case (Starting by 1), followed by Q lines with the answer of each query. If the query was

a modification query, then you should output "OK" (Quotes for clarity), otherwise, output the

sum of the number from A to B inclusive.

The output must be written to standard output.

INPUT OUTPUT
2
4 4
answer 1 4
modification 1 2
modification 2 3
answer 2 2
8 6
modification 2 4
modification 4 8
modification 4 5
answer 8 8
modification 5 7
answer 4 8
Scenario #1:
0
OK
OK
2
Scenario #2:
OK
OK
OK
1
OK
11
Constraints
• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000

 

 


hide comments
naruto09: 2016-03-24 12:24:59

finally AC..great question indeed..C++ users try to avoid the use of cin or cout..

Sunil: 2015-04-13 19:20:55

same as horrible

humble_coder: 2014-11-04 15:24:18

@Tjandra
and how does that spped trick work..??

Rocker3011: 2014-07-04 02:49:51

i knew this was doable with a boosted fenwick tree, such a nice problem to practice!!!!!

brahim: 2013-01-30 10:24:23

Is A is always less than B?

Mukund Kumar: 2013-01-03 07:13:34

can anyone please explain the output for answer query??
thanks in advance!!

(Tjandra Satria Gunawan)(曾毅昆): 2013-01-02 22:14:38

phew... It's very hard for me to speed up until faster than 0.97s... finally #1st place (0.9s) after 44 attempts. now I have a new speed trick for "tree-type" data structure ;-)


Added by:Venezuelan Programming League
Date:2012-10-27
Time limit:0.150s-0.452s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for UCV-CEIDEC contest.