1468C.md (3470B)
1 Source: https://codeforces.com/problemset/problem/1468/C 2 3 C. Berpizza 4 5 time limit per test 6 7 5 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Monocarp and Polycarp are working as waiters in Berpizza, a pizzeria located near the center of Bertown. Since they are waiters, their job is to serve the customers, but they choose whom they serve first differently. 22 23 At the start of the working day, there are no customers at the Berpizza. They come there one by one. When a customer comes into the pizzeria, she sits and waits for Monocarp or Polycarp to serve her. Monocarp has been working in Berpizza for just two weeks, so whenever he serves a customer, he simply chooses the one who came to Berpizza first, and serves that customer. 24 25 On the other hand, Polycarp is an experienced waiter at Berpizza, and he knows which customers are going to spend a lot of money at the pizzeria (and which aren't) as soon as he sees them. For each customer, Polycarp estimates the amount of money this customer can spend, and when he serves a customer, he chooses the one that is expected to leave the most money at Berpizza (in case there are several such customers, he chooses the one who came first among them). 26 27 Obviously, no customer can be served twice, so Monocarp and Polycarp choose which customer to serve only among those who haven't been served yet. 28 29 When the number of customers gets really high, it becomes difficult for both Monocarp and Polycarp to choose the customer they are going to serve. Your task is to write a program that makes these choices for them. Formally, your program should be able to process three types of queries: 30 31 * $1$ $m$ — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $m$; 32 * $2$ — Monocarp serves a customer which came to the pizzeria first; 33 * $3$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are several such customers, the one that came to the pizzeria first is chosen). 34 35 For each query of types $2$ and $3$, report the number of the customer who was served (the customers are numbered in the order they come to the pizzeria, starting from $1$). 36 37 Input 38 39 The first line contains one integer $q$ ($2 \le q \le 5 \cdot 10^5$) — the number of queries. 40 41 Then $q$ lines follow, each describing a query in one of the following formats: 42 43 * $1$ $m$ ($1 \le m \le 5 \cdot 10^5$) — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $m$; 44 * $2$ — Monocarp serves a customer which came to the pizzeria first; 45 * $3$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are multiple such customers, the one that came to the pizzeria first is chosen). 46 47 Queries of type $2$ and $3$ are asked only when there exists at least one customer that hasn't been served yet. There is at least one query of type $2$ or $3$ in the input. 48 49 Output 50 51 For each query of type $2$ or $3$, print one integer — the number of the customer that has been served in that event. The customers are numbered in the order in which they come to the pizzeria, starting from $1$. 52 53 Examples 54 55 Input 56 57 ``` 58 8 59 1 8 60 1 10 61 1 6 62 3 63 2 64 1 9 65 2 66 3 67 ``` 68 69 Output 70 71 ``` 72 2 1 3 4 73 ``` 74 75 Input 76 77 ``` 78 6 79 1 8 80 1 10 81 1 8 82 3 83 3 84 3 85 ``` 86 87 Output 88 89 ``` 90 2 1 3 91 ``` 92 93 Input 94 95 ``` 96 8 97 1 103913 98 3 99 1 103913 100 1 103913 101 3 102 1 103913 103 1 103913 104 2 105 ``` 106 107 Output 108 109 ``` 110 1 2 3 111 ```