trang chủ / đề bài / icpc26_mn_i

Những lớp bị mất

Đề bài

Mô tả

Linh đang khôi phục một dự án video có tệp bị hỏng. Dự án có n đoạn phim (clip), đánh số từ 1 đến n. Mỗi clip nằm trên một lớp (layer) riêng, và các lớp được xếp chồng lên nhau: khi nhiều clip cùng xuất hiện trên màn hình ở cùng một khung hình, clip ở lớp cao hơn sẽ che các clip ở bên dưới. Clip i xuất hiện trên màn hình ở các khung hình li,li+1,…,ri, tính cả li và ri.

Khoảng khung hình của các clip vẫn còn nguyên, nhưng thứ tự của các lớp đã bị mất. Linh vẫn còn nhật ký của trình kết xuất xem trước (preview renderer). Mỗi dòng của nhật ký là một ảnh chụp (snapshot) được lấy tại một khung hình x nào đó. Nó liệt kê các clip đang xuất hiện trên màn hình ở khung hình x, bắt đầu từ lớp trên cùng đi xuống, nhưng dừng lại sau k clip đầu tiên. Giá trị k có thể khác nhau giữa các ảnh chụp. Nó có thể bằng 0, và có thể bằng số clip đang có trên màn hình, khi đó tất cả các clip đều được liệt kê.

Hãy giúp Linh tìm một thứ tự của cả n lớp, từ trên xuống dưới, phù hợp với mọi ảnh chụp. Một thứ tự phù hợp với ảnh chụp (x,k,s1,…,sk) nếu điều sau đúng: lấy các clip i có li≤x≤ri và sắp xếp chúng từ trên xuống dưới theo thứ tự đó; khi đó k clip đầu tiên lần lượt là s1,s2,…,sk, đúng theo thứ tự này. Nói riêng, nếu k≥1 thì mọi clip đang có trên màn hình ở khung hình x mà không thuộc s1,…,sk đều phải nằm dưới clip sk. Một ảnh chụp có k=0 không đặt ra ràng buộc nào lên thứ tự.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên n (1≤n≤3·105): số clip.
  • Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên li và ri (0≤li<ri≤109): khung hình đầu tiên và khung hình cuối cùng của clip i.
  • Dòng tiếp theo chứa một số nguyên m (1≤m≤3·105): số ảnh chụp.
  • Mỗi dòng trong m dòng tiếp theo mô tả một ảnh chụp. Dòng bắt đầu bằng hai số nguyên x và k (0≤x≤109, 0≤k≤n): khung hình của ảnh chụp và số clip được liệt kê. Tiếp theo là k số nguyên s1,s2,…,sk (1≤sj≤n): các clip được liệt kê từ trên xuống dưới. Các clip s1,…,sk đôi một phân biệt, và mỗi clip trong số đó đều đang xuất hiện trên màn hình ở khung hình x. Nếu k=0, dòng chỉ chứa x và k.

Các ảnh chụp được cho theo thứ tự x không giảm; có thể có nhiều ảnh chụp ở cùng một khung hình. Tổng các giá trị k trên mọi ảnh chụp không vượt quá 106.

Dữ liệu đảm bảo có ít nhất một thứ tự phù hợp với mọi ảnh chụp.

Dữ liệu ra

In ra n số nguyên phân biệt p1,p2,…,pn: số hiệu các clip từ lớp trên cùng đến lớp dưới cùng. Nếu có nhiều thứ tự phù hợp với mọi ảnh chụp, in ra thứ tự bất kỳ.

Ràng buộc

  • 1≤n≤3·105, 1≤m≤3·105.
  • 0≤li<ri≤109.
  • 0≤x≤109, 0≤k≤n, các ảnh chụp có x không giảm.
  • Tổng các giá trị k không vượt quá 106.
  • Các clip được liệt kê trong một ảnh chụp đôi một phân biệt và đều xuất hiện trên màn hình ở khung hình của ảnh chụp đó.
  • Luôn tồn tại ít nhất một thứ tự phù hợp.

Ví dụ

Input Output Giải thích
5
2 6
0 4
4 9
6 8
1 10
4
1 1 2
4 1 3
6 1 4
9 2 3 5
4 3 2 5 1 Ở khung hình 1, clip 2 và 5 xuất hiện, nên clip 2 ở trên clip 5. Ở khung hình 4, các clip 1,2,3,5 xuất hiện (clip 2 kết thúc và clip 3 bắt đầu ở khung hình này), và clip 3 ở trên cùng. Ở khung hình 6, các clip 1,3,4,5 xuất hiện (clip 1 kết thúc và clip 4 bắt đầu ở khung hình này), và clip 4 ở trên cùng. Ở khung hình 9, chỉ có clip 3 và 5 xuất hiện, và ảnh chụp liệt kê cả hai. Ngoài thứ tự trong ví dụ, các thứ tự 4 3 1 2 5 và 4 3 2 1 5 cũng được chấp nhận.
4
0 5
5 10
3 7
20 30
4
0 0
5 1 3
5 2 3 2
12 0
3 2 4 1 Các ảnh chụp ở khung hình 0 và 12 không liệt kê clip nào, còn hai ảnh chụp ở khung hình 5 thấy các clip 1,2,3. Gộp lại, chúng cho biết clip 3 ở trên clip 2, và clip 2 ở trên clip 1. Không ảnh chụp nào thấy clip 4, nên clip 4 có thể nằm ở vị trí bất kỳ trong thứ tự.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0