| Fişierul intrare/ieşire: | expectedgoals.in, expectedgoals.out | Sursă | IIOT 2021-22 Runda 2 |
| Autor | Stefan Dascalescu | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | expectedgoals.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.
