Binary indexed tree problem

Правка ru2, от feruz.atamuradov, 2017-11-02 14:59:06

Hi CF community. I found problem tag of binary indexed tree. I have not any ideas. Help me!
TASK

(Time: 0.4 seconds Memory: 16 MB)

In one military unit they decided to build one line in order of growth. Because part was far from exemplary, the soldiers often came in bad time, and then they had to be thrown out of the ranks for badly polished boots. However, soldiers in the process of arrival and departure should always have been built according to growth — at first the highest, and at the end — the lowest. For the placement of soldiers the ensign answered, who noticed an interesting feature — all the soldiers in a part of different growth.

Your task is to help the ensign correctly deploy the soldiers, namely for each incoming soldier to indicate before which soldier in the formation he should become.

Input

The first line of the input file INPUT.TXT contains the number N — the number of instructions (1 ≤ N ≤ 30 000). Each next line contains a description of the command: the number 1 and X, if the soldier comes into service (X is the soldier's growth, the natural number is up to 100,000 inclusive) and the number 2 and Y, if the soldier standing in the ranks in place of Y must be removed from service (soldiers in the unit are numbered from scratch).

Output

Output the output OUTPUT.TXT in a separate line for each command 1 (adding to the order) number K — the number of the position to which this soldier should stand (all those behind him move backwards).

Tests have in task. Thanks in advance!

Теги binary indexed tree, fenwick tree, acmp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru3 Русский feruz.atamuradov 2017-11-02 15:01:29 2139
ru2 Русский feruz.atamuradov 2017-11-02 14:59:06 1501
ru1 Русский feruz.atamuradov 2017-11-01 15:09:30 266 Первая редакция (опубликовано)