QMAX3VN - Giá trị lớn nhất 3

no tags 

Tiếp tục hành trình khám phá sức mạnh của các cấu trúc dữ liệu đặc biệt, hai nhà thám hiểm pirateduyhung123abc lại lao vào những thử thách với những bài toán hóc búa mới. Nhưng những gì họ thu thập được chẳng là bao. Chán chường và bế tắc, họ quyết định lật giở những bài toán đã giải để xem lại những thành quả đã đạt được. Đột nhiên, một thứ ánh sáng lạ kì lóe lên trong đầu họ: "Tại sao không kết hợp một số bài toán lại với nhau !" . Và đây, QMAX3VN đã ra đời, tự nhiên như cái cách mà lửa đã đến với loài người.

Chuyện kể rằng vào một buổi sáng nọ trong một doanh trại quân đội, các quân nhân đang tập trung thành một hàng ngang để chuẩn bị tập thể dục buổi sáng. Nhưng vấn đề là không phải tất cả họ đều dậy cùng một lúc. Ban đầu, hàng ngang chẳng có người nào. Sau một lúc, lại có một anh chàng quân nhân hộc tốc chạy ra. Mỗi anh chàng lại thích đứng cạnh ai đó, nên cứ nhất quyết chen vào một vị trí nào đó trong hàng. Thật là một cảnh tượng hỗn độn và không thể chấp nhận. Mặt ai cũng cúi gằm xuống đất chuẩn bị chịu sự trừng phạt của viên chỉ huy. Viên chỉ huy, tuy nghiêm khắc nhưng cũng rất nhân hậu, đã đưa một trò chơi như sau để cho các anh chàng một bài học. Mỗi khi ông ta đưa ra một khẩu lệnh (x,y) thì lập tức các quân nhân phải chỉ vào người cao nhất trong các quân nhân đang đứng từ vị trí x đến vị trí y trong hàng. Khẩu lệnh sẽ được phát ra liên tục từ khi có một quân nhân bước vào hàng. Hình phạt đang chờ những người làm sai khẩu lệnh. Sân tập ướt đẫm những giọt mồ hồi lo lắng của các cậu lính trẻ. Họ đang cần sự giúp đỡ của bạn!

Input

Dữ liệu vào gồm nhiều dòng:

  • Dòng thứ 1 : Một số nguyên n (1 ≤ n ≤ 100000): Số sự kiện sẽ diễn ra trong buổi tập thể dục.
  • Dòng thứ 2 đến dòng thứ n+1: Mỗi dòng là một trong hai sự kiện:
    • A x y : Một quân nhân có chiều cao x vừa chen vào giữa vị trí thứ y-1 và y trong hàng (-109 ≤ x ≤ 109; 1 ≤ y ≤ k+1 , với k là số anh lính hiện có trong hàng).
    • Q x y : Khẩu lệnh của viên chỉ huy. Hãy tìm chiều cao của người cao nhất trong các quân nhân đang đứng từ vị trí thứ x đến vị trí thứ y trong hàng (1 ≤ x ≤ y ≤ k , với k là số anh lính hiện có trong hàng).

 

Output

Dữ liệu ra gồm nhiều dòng:

  • Với mỗi khẩu lệnh của viên chỉ huy, ghi trên một dòng chiều cao của người mà các quân nhân cần phải chỉ vào.

 

Example

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


hide comments
vipulvikram: 2018-06-27 17:32:59

Thanks.
Use printf and scanf else you will get timeout in testcase 10;

Shubhashsi Roy Dipta: 2018-02-03 17:16:37

easy one, but don't use getchar(), otherwise you will get RE

Anton Logunov: 2016-12-26 16:20:35

Please add C++14 for allowed languages.

kejriwal: 2016-05-02 09:45:00

fast i/o gets AC :D

Rajat De: 2015-07-15 14:59:27

theres something wrong with the input , there are characters other than A and Q

Tuukka Korhonen: 2015-01-13 13:51:04

How it is possible to get accepted when the time limit is only 0.128 seconds?
--(Francky)--> Time limit is for each input file. Then your cumulative timing can be greater than 0.128 and get AC if all files are done under 0.128s. Good luck.

Last edit: 2015-01-13 14:00:12
Alex Abbas: 2014-03-06 04:02:10

soldiers with negative height that was fun to notice... 3 or 4 WAs

aristofanis: 2014-02-01 11:31:32

Great problem!

Abdullah Enes ÖNCÜ: 2014-01-11 22:33:20

why i get rte on 10?

Hayk Saribekyan: 2012-01-04 19:14:52

translate.google.com says that in English problem name will be "Maximum Value 3"


Added by:khanhptnk
Date:2009-05-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE
Resource:Sưu tầm