Description
Note.
To improve the performance of I/O operations using cin / cout from the iostream, you can add the following lines of code to your program. Please note that after adding these lines, you should avoid using I/O functions in C such as printf / scanf.
int main() {
std::cin.tie(NULL);
std::ios::sync_with_stdio(false);
/* your program */
}
Hodilo is a well-known hot pot restaurant, and it's extremely challenging to have a table during peak dining hours in Hodilo. Even though, the restaurant does not accept reservations in advance, requiring every guest to visit the restaurant, take a number, and wait for their turn. Hodilo is opening a new branch in Hsinchu, and you have been invited to design a queuing system, which helps assign a table to each guest.
The provided data consists of the arrival record of each guest at the restaurant. Additionally, each guest at Hodilo has a membership level, and their arrival time is unique. We will add them to the waiting list one by one and subsequently assign tables to the guests on the waiting list. Here's how we assign guests from the waiting list to tables:
- We will sort the waiting list based on the order in which guests arrive.
- Whenever a new guest arrives or some occupied tables are released, the following procedure is performed to see if any table assignment is possible:
if the first guest on the waiting list can be accommodated by some empty tables:
assign the smallest empty table that can accommodate the first guest
else if the first guest is willing and able to share a table with others:
/* Subtask 3: Check the description below */
else if some other guests on the waiting list can be accommodated by some empty tables:
from those guests who can be accommodated, sort them according to the following rule
membership level (high to low) -> group size (large to small) -> arrival time (early to late)
assign the smallest empty table that can accommodate the first guest in the above sorted list
else break
}
Since we have access to the latest AI technology, we can accurately estimate the dining duration for each customer. By utilizing this information, we can determine the length of time each customer will occupy their table. As soon as a guest's dining time ends, we assume that the table can be cleared instantly, making it available immediately.
Your task is to assist Hodilo in implementing this system and provide the estimated time when each customer can be seated at their table, allowing them to indulge in the delicious hot pot experience.
Please take a look at the following GIF demonstration for a better understanding of the sample I/O 1. (fifth value = 0)
Notice for subtask 3.
The fifth value in the arrival record of each guest indicates their willingness to share a table with others (0: not willing / 1: willing). Here's how we determine if a guest is able to share a table with others:
| Select the tables that are currently occupied by other guests and have the fewest remaining seats, while also being able to accommodate the new guest. |  |
| If there are multiple tables with the same fewest remaining seats, choose the table where the earliest arrival time for all the guests at the same table is the earliest. |  |
Make sure that these occupied guests are also willing to share a table with others. |
 |
Input
The first line contains two integers N and M - the number of guests and the number of table types.
For each of the next N lines, the i-th line represents the i-th guest arrival at the restaurant. It’s given in the following format:
<arrival timestamp> <group size> <dining duration> <membership level> <table sharing willingness>
We use an integer to represent the timestamp. The timestamp of a guest being seated at a table plus their dining duration will determine when the table becomes available again.
Each of the next M lines represents the number of the tables for each size in the restaurant. It’s given in the following format:
<table size> <number of tables>
Output
Output N lines, where the i-th line shows the timestamp when the i-th guest can have their table.
Constraints
- 1 ≤ N ≤ 2 × 105, 1 ≤ M ≤ 103
- Guests
- 0 ≤
arrival timestamp≤ 109 (The given arrival time is in increasing order) - 1 ≤
group size≤ max(table size) - 1 ≤
dining duration≤ 103 - 0 ≤
membership level≤ 5 table sharing willingness∈ {0, 1}
- 0 ≤
- Tables
- 1 ≤
table size≤ 103 - 1 ≤
number of tables≤ 10
- 1 ≤
- It's guaranteed that the answer will not exceed 109
Subtasks
- Subtask 1 (50%)
membership level= 0table sharing willingness= 0
- Subtask 2 (25%)
table sharing willingness= 0
- Subtask 3 (25%)
- No additional constraints