TLEoj Cup Final Day 2 - Tráo bài

Điểm: 2100 (thành phần)

Thời gian: 2.25s

Bộ nhớ: 256M

Input: SHUF.inp

Output: SHUF.out

Tác giả:

Sunlight

Dạng bài

khanhphucscratch muốn tặng cho moi_hoc_code một món quà đặc biệt nhân ngày sinh nhật của bạn ấy, ngày 10 tháng 1 năm 2024. Vì không nghĩ ra được món quà nào đặc sắc nên khanhphucscratch chỉ đành tặng moi_hoc_code một chồng bài gồm $n$ là bài được đánh số từ $1$ đến $n$ theo thứ tự từ trên xuống dưới. Vì món quà chưa đủ ấn tượng, khanhphucscratch quyết định mời moi_hoc_code giúp mình thực hiện một thử thách. moi_hoc_code sẽ thực hiện $q$ lần tráo bài, mỗi lần cô sẽ rút $c_i$ các lá bài có thứ tự từ $l_i$ đến $l_i + c_i - 1$ từ trên xuống dưới và chèn chồng bài vào trên lá bài thứ $k_i$ trong số các lá bài còn lại (nếu $k_i = n - c_i + 1$ thì chồng bài sẽ được chèn vào dưới những lá bài còn lại). moi_hoc_code muốn khanhphucscratch xác định $t$ lá bài đầu tiên của chồng bài sau khi xáo.

Input, Output và Subtask

Input (SHUF.inp)

Dòng đầu tiên gồm ba số nguyên dương $n, t, q$ $(n, q \le 10^5, t \le n)$ .
$q$ dòng tiếp theo, dòng thứ $i$ gồm ba số nguyên dương $l_i, c_i, k_i$ $(l_i + c_i - 1 \le n, k_i \le n - c_i + 1)$

Output (SHUF.out)

Một dòng gồm $t$ số nguyên dương là số ghi trên $t$ lá bài đầu tiên sau khi tráo.

Subtask

Subtask 1 $(30\%)$ : $n, q \le 5000$ .
Subtask 2 $(40\%)$ : $t \le \min(n, 50)$ .
Subtask 3 $(30\%)$ : Không có giới hạn gì thêm.

Sample 1

Input (SHUF.inp)

5 5 2
3 2 2
3 3 1

Output (SHUF.out)

4 2 5 1 3

Notes

$(1, 2, 3, 4, 5) \rightarrow (1, 3, 4, 2, 5) \rightarrow (4, 2, 5, 1, 3)$

Bình luận đầu tiên

Bình luận

Không có bình luận nào.