Vampiric politicians P39136


Statement
 

pdf   zip

thehtml

In a country far away, some politicians seem to be eternal. After a thorough study, the reason has finally been found out: they are vampires. The cementery where they rest has been located. Can you help to exterminate as many of them as possible, by thrusting a long silver pike vertically through the ground?

For simplicity, let us consider a two-dimensional world. For each vampire, we know the beginning and the end of its body when resting horizontally in its tomb. All ‍the vampires rest at diferent depths, which are irrelevant.

To the right you can see the first case of the sample. When the four vampires are resting, we can happily kill them all.

(12,7) unit=0.5, linewidth=0.8

linecolor=black [fillcolor=brown,fillstyle=solid](0,0)(12,0)(12,5)(0,5)

linewidth=2.4

linecolor=green [fillcolor=green,fillstyle=solid](1,1)(9,1)(9,1.2)(1,1.2)

linecolor=red [fillcolor=red,fillstyle=solid](3,3)(6,3)(6,3.2)(3,3.2)

linecolor=lila [fillcolor=lila,fillstyle=solid](5,2)(11,2)(11,2.2)(5,2.2)

linecolor=yellow [fillcolor=yellow,fillstyle=solid](4,4)(7,4)(7,4.2)(4,4.2)

linecolor=gray ->(5.5,6)(5.5,-1)

Input

Input consists of several cases. Each case starts with the number of vampires n. Follow n ‍triples si, ℓi, ri, with the name, the left extreme and the right extreme of each vampire when resting. You can assume 1 ≤ n ≤ 104, that all si are different and made up of between 1 and 12 lowercase letters, and 0 ≤ ℓi < ri ≤ 109.

Follow between 1 and 105 names of vampires. Initially, the cemetery is empty. Each given name s indicates that the vampire s enters the cementery if s was not already there, or that s ‍leaves the cemetery otherwise. The word “END” marks the end of each case.

Output

After each given vampire name s, print the maximum number of vampires that could be killed at that moment. Print a line with 10 dashes at the end of each case.

Public test cases

  • Input

    4
perista 0 8
inconsolable 2 5
bucolica 4 10
camallarg 3 6
perista
bucolica
camallarg
inconsolable
bucolica
END
5
a 0 500000000
b 500000000 1000000000
c 0 499999999
d 23 42
e 0 499999999
b
b
a
b
c
a
e
END

    Output

    1
2
3
4
3
----------
1
0
1
2
2
1
2
----------
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++