Тема: STL и приложение за решаване на състезателни задачи

Задача 1.
Една компания има информационна система за поддържане на състава на персонала. Основна функционална част от системата дефинирата със следните операции:
    A <ЕГН> : добави нов служител към системата с даденото ЕГН, ако той не е в системата;
    D <ЕГН> : изтрии служител от системата с даденото ЕГН, ако такъв служител е вече в системата;
    I <ЕГН> <ЕГН> : изведи броя на служителите, родени между дадените ЕГН, или години по формат YY00000000 ZZ99999999 за интервала между години YY и ZZ включително;
    M : изведи ЕГН на най-стария служител;
    М <число> : изведи <число> ЕГН-та на <число> най-стари служители, наредени в ред: на първо място - най стария;
    N : изведи броят на всички служители в компанията.
Напишете програма за поддържане на информационната система.

Вход
На входа има редица от команди към системата (не повече от 108).

Изход
За всяка командите I, M и N от входа на изхода се извеждат необходимите данни, по една данна на ред.

Пример:
A 5108121200
A 6209012222
A 7801029823
N
M
I 5000000000 6099999999
I 5000000000 6299999999
A 5109220909
M 2
N
D 5109220908
N
A 5109220909
N
D 5109220909
N

Решение на примера:
3
5108121200
1
2
5108121200
5109220909
4
4
4
3

Задача 2.
Choosing a camera
Mr. Strange is choosing a compact digital photo camera. He looks at various shops offers and sometimes makes temporary choices. At each temporary choice, he knows about all offers he already saw, but doesn’t know about those he will see in the future. According to Mr. Strange, any digital camera is fully  described by two properties: the number of pixels and the optical zoom ratio. For each property,  he thinks that the  more is the better. Mr. Strange is afraid to buy an outdated camera, so he never chooses a camera, if he knows about another camera, which is strictly better by any one property and not worse by another. Among all cameras Mr. Strange does not consider outdated, he chooses the cheapest one; if there are different non-outdated cameras with equal minimal cost, he  chooses among them the oldest offer.
The first line of input contains the number of the test cases. The first line of each test case contains total number n (1 ≤ n ≤ 105) of actions. Each action can be either a new camera offer or a temporary choice. Each offer is denoted by big letter P, then camera’s number of pixels, zoom ratio  and cost. Each temporary choice is denoted by big letter  С. Each action is denoted in separate line, data inside lines are separated by single spaces. Numbers of pixels are integers in the range 103≤ pi ≤ 109. Zoom ration is a floating-point number in  the range  1 ≤  zi ≤ 100, with no more than  6 digits after decimal point. Costs are integers in the range 1 ≤ ci ≤ 106. Size of the input is less than 16 Mb.
For each temporary choice  action, your program should output the number of the action when the currently chosen camera was offered. If no choice can be done according to the rules, the query result should be –1. All results inside each test case should be written in the same line and separated by single spaces. Results for consecutive test cases should be in consecutive lines.

Sample input
2
1
P 9600000 7 72
7
P 1200000 1 40
P 7200000 5 100
C
P 9600000 3 200
C
P 7200000 12 220
C


Sample output
2 2 4

The first line of the output is empty, because first test case contain no C actions. At the first choosing in second test case, offer 1 (1200000 1 40) is outdated, so 2 (7200000 5 100) is the best because the only. At the 2-nd, the same choice, because it’s cheaper than 4 (9600000 3 200). At the 3rd, 6 (7200000 12 220) makes 2 (7200000 5 100) outdated, so 4 (9600000 3 200) becomes the cheapest among non-outdated.