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.
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.
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.
answer 1 4
modification 1 2
modification 2 3
answer 2 2
modification 2 4
modification 4 8
modification 4 5
answer 8 8
modification 5 7
answer 4 8
finally AC..great question indeed..C++ users try to avoid the use of cin or cout..
same as horrible
i knew this was doable with a boosted fenwick tree, such a nice problem to practice!!!!!
Is A is always less than B?
can anyone please explain the output for answer query??
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
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 ;-)