codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```