QMAX3VN - Giá trị lớn nhất 3
Following the journey to explore the real power of special data stuctures, two adventurers pirate and duyhung123abc continued to find new challenges with new more and more complicated problems. But what they earned was unremarkable. Being tired and stucked, they decided to review the problems they had solved to see what they had had so far. Suddenly, a mysterious light came to their mind: "why not combine some of them into one !". And here, QMAX3VN was born, as natural as the way fire had come to humankind.
It is said that in a morning at a military camp. All soldiers were gathering in a line to prepare for morning excercises. But the problem was they did not get up simultaneously. The line was initially empty. After sometime, a soldier got up and ran hurrily to join the line. Also, each of them liked to stand near their friends so they would elbow themselves to some position of the current line. What a messy and unacceptable scene for a military camp! The soldiers knew what they had done and were ready to be punished. The strict commander decided to give them a lesson. Everytime he gave an order(x,y), all soldiers in the line had to say loudly the height of the highest man among those were standing from position x to position y. Orders were made continuously since the first soldier entered the line. Punishment was waiting for whom would carried out the order incorrectly. The yard was full of worry from young soldiers. They really needed help !
The input contains several lines:
- Line 1 : An integer n (1 ≤ n ≤ 100000): The number of events occuring in that morning.
- Line 2 to line n+1: Each line is one of the following two events:
- A x y : A soldier with height x had just entered the line and elbowed himself into the position between position y-1 and position y of the line (-109 ≤ x ≤ 109; 1 ≤ y ≤ k+1 , k denotes the number of soldiers in the line right before this soldier came).
- Q x y : An order of the commander. Find the height of the highest man among those were standing from position x to position y of the line (1 ≤ x ≤ y ≤ k , k denotes the number of soldiers was currently in the line).
The output contains several lines:
- For each order of the commander, write in one line the number all soldiers had to say loudly.
Input: 10 A 1 1 A 2 2 Q 1 2 A 3 1 A 4 3 Q 2 4 A 5 2 Q 2 3 A 6 3 Q 1 4 Output: 2 4 5 6
Shubhashsi Roy Dipta:
easy one, but don't use getchar(), otherwise you will get RE
Please add C++14 for allowed languages.
fast i/o gets AC :D
theres something wrong with the input , there are characters other than A and Q
How it is possible to get accepted when the time limit is only 0.128 seconds?
soldiers with negative height that was fun to notice... 3 or 4 WAs
Abdullah Enes ÖNCÜ:
why i get rte on 10?
translate.google.com says that in English problem name will be "Maximum Value 3"
Is it possible to give this problem an English title?
|Added by:||Nguyễn Xuân Khánh|
|Cluster:||Cube (Intel G860)|
|Languages:||ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP clisp LISP sbcl D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE|