Fişierul intrare/ieşire:expectedgoals.in, expectedgoals.outSursăIIOT 2021-22 Runda 2
AutorStefan DascalescuAdăugată destefdascalescuStefan Dascalescu stefdascalescu
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Goal Statistics

Lately, Stefan has been interested in studying football statistics and one day, he discovered a new metric called "expected goals" xG. In order to see how can xG affect football games, he gathered data from various football games and now he needs your help to process the data he got.

In order to start the research, he told you that there will be q events during the football season, and the events are of two types:

1 k: His database gets a scoring chance worth k xG. Since xG is usually represented as a real number, he gave you its value multiplied by 106, so that k is an integer. Therefore, k can be between 1 and 106, on a probability scale from 10^-6 to 1 (the probability can never be equal to 0).

2 p: He wants to find the smallest amount of xG needed in order for a team to score p goals, if we assume that all the scoring chances have been converted into goals.

The database became really big and Stefan got into trouble, so it's up to you to help him!

Date de intrare

The first line of the input file expectedgoals.in contains q, the number of queries 1 ≤ q ≤ 10^6.

The next q lines of the input contain two integers type and k 1 ≤ type ≤ 2, 1 ≤ k ≤ 106, 1 ≤ p ≤ 106. For type 2, p is guaranteed to be at most equal to the number of events of type 1 which happened already before the current query.

Date de ieşire

The output file expectedgoals.out will contain on each line, the answers for the queries of type 2, in the order from the input.

Restricţii

  • For tests worth 30 points, 1 ≤ q ≤ 2 * 10^3, 1 ≤ k ≤ 100.
  • For tests worth 30 more points, 1 ≤ k ≤ 100.

Exemplu

expectedgoals.inexpectedgoals.out
10
1 20
1 8
1 14
1 11
2 3
1 5
1 8
1 11
2 5
2 7
33
43
77

Explicaţie

After the first 5 queries, the array is 20, 8, 14, 11. The smallest amount of xG we can get from 5 values is obtained by taking 8, 11 and 14 and the xG sum is 33.

After the first 9 queries, the array is 20, 8, 14, 11, 5, 8, 11. The smallest amount of xG we can get from 5 values is obtained by taking 8, 11, 5, 8 and 11 and the xG sum is 43.

After the first 10 queries, the array is 20, 8, 14, 11, 5, 8, 11 and we have to take every single value, and the sum is 77.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?