Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TTRAVEL - Time Travel

Farmer John (FJ) vừa mua đuợc một cái cỗ máy thời gian. FJ có thể tiến tới một thời gian nào đó trong tuơng lai bằng cách cứ cho thời gian trôi (không thể sử dụng máy thời gian vì tuơng lai chưa định sẵn/bị đảo lộn) hoặc quay trở lại mốc thời gian nào đó trong quá khứ.

            FJ  muốn đạt đuợc sản luợng nhiều nhất có thể . Vì thế anh ấy đã thống kê , ghi lại sản lụơng những con bò cung cấp trong quá trình nuôi hoặc sau khi có một truy vấn hành động nào đó làm tác động đến đàn bò. FJ chỉ quan tâm đến chỉ số ID của con bò mà anh ấy nuôi trong thời gian ngắn nhất . Hãy viết chuơng trình xác định và in ra các số ID ấy sau mỗi truy vấn hành động (hoặc in ra -1 nếu FJ chẳng còn con bò nào !)

            FJ có tập gồm N (1 ≤ N ≤ 80,000) sự kiện đuợc đánh số từ 1..N thể hiện sự thay đổi trong đàn bò theo thời gian biểu của FJ. Mỗi truy vấn đuợc ghi trên một dòng gồm có một kí tự c và một số nguyên K  (1 ≤ K ≤ 100,000) nếu như c = ‘a’ hoặc c = ‘t’ . Các sự kiện có sau

-          Nếu c = ‘a’ thì John thêm một con bò có số ID là K vào đàn bò.

-          Nếu c = ‘s’ thì John bán đi con bò có số ngày nuôi ít nhất.

-          Nếu c = ‘t’ thì John dùng cỗ máy thời gian trở lại thời điểm truớc khi thực hiện truy vấn K và đàn bò sẽ trở lại như lúc thời điểm truớc K .

Input

- Dòng đầu tiên ghi số nguyên N

- N dòng tiếp theo ghi các truy vấn

 Output

- Gồm N dòng . Mỗi dòng ghi số ID của con bò có ngày nuôi ngắn nhất 

------------------------------------------------------------------------

Ta có ví dụ sau . Với N = 12 và các truy vấn , ta có output sau

 

    #   T.vấn   Đàn bò      Kết quả     Giải thích
     1   a 5  -> [5]        => 5        Thêm một con bò có ID = 5
     2   a 3  -> [5,3]      => 3        Thêm một con bò có ID = 3
     3   a 7  -> [5,3,7]    => 7        Thêm một con bò có ID = 7
     4   s    -> [5,3]      => 3        Bán con bò có ID = 7
     5   t 2  -> [5]        => 5        Quay ngụơc thời gian truớc #2
     6   a 2  -> [5,2]      => 2        Thêm một con bò có ID = 2
     7   t 4  -> [5,3,7]    => 7        Quay ngụơc thời gian truớc #4
     8   a 4  -> [5,3,7,4]  => 4        Thêm một con bò có ID = 4
     9   s    -> [5,3,7]    => 7        Bán con bò có ID = 4
    10   t 7  -> [5,2]      => 2        Quay ngụơc thời gian truớc #7
    11   s    -> [5]        => 5        Bán con bò có ID = 2
    12   s    -> []         => -1       Bán con bò có ID = 5

 

Input

Output

12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s
5
3
7
3
5
2
7
4
7
2
5
-1

 


Được gửi lên bởi:Buồn
Ngày:2010-04-23
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC GAWK MAWK BC C-CLANG C NCSHARP CPP CPP14-CLANG CLOJURE COBOL COFFEE D-CLANG D-DMD DART ELIXIR FSHARP FANTOM FORTH GO GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC-CLANG OCT PAS-FPC PDF PICO PS PROLOG PYPY3 PYTHON3 PY_NBC R RACKET CHICKEN SWIFT TEXT UNLAMBDA VB.NET
Nguồn bài:USACO US Open 2010

hide comments
2010-04-29 07:42:28
PS ơi, em nhầm ở cách giải thích truy vấn 9 và 11 rồi kìa (test vẫn đúng).
2010-04-29 05:03:45 Nguyen Duc Tam
bài này quá dễ để AC. Mặt dù tôi tệ.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.