Đề bài

Trên mặt phẳng có một sóc bay và \(N\) cột thẳng đứng vô hạn, đánh số từ \(0\) đến \(N-1\). Chân cột \(i\) ở \((i,0)\). Nếu \(B[i]=0\), cột có màu đỏ; nếu \(B[i]=1\), cột có màu xanh.

Ban đầu sóc ở \((0,0)\) và cần đến \((N,H)\). Khi không ở vị trí có cột, sóc bay sang phải và giữ nguyên độ cao, mất thời gian \(0\). Tại cột \(i\), sóc phải chọn một trong các hành động:

• Bay qua cột, không đổi độ cao và mất thời gian \(0\).
• Nếu cột đỏ, trèo lên làm độ cao tăng \(1\), mất \(A[i]\) thời gian.
• Nếu cột xanh, nhảy làm độ cao tăng \(1\), mất \(A[i]\) thời gian.

Khi đi qua vị trí ngang \(i+0.5\), độ cao phải nằm trong đoạn \([L[i],R[i]]\). Khi đến vị trí ngang \(N\), độ cao phải đúng bằng \(H\).

Với mỗi \(k=0,1,\ldots,H\), gọi \(T[k]\) là thời gian nhỏ nhất của một hành trình hợp lệ dùng đúng \(k\) lần nhảy trên cột xanh. Nếu không tồn tại hành trình như vậy, đặt \(T[k]=-1\).

Hãy tìm \(T[0],T[1],\ldots,T[H]\).

Yêu cầu cài đặt

vector<long long> fly(
    int H,
    vector<int> A,
    vector<int> B,
    vector<int> L,
    vector<int> R
);

Các mảng có cùng độ dài \(N\). Hàm phải trả về mảng \(T\) có độ dài \(H+1\), được gọi đúng một lần, và chương trình nộp không được thực hiện thao tác vào/ra.

Ràng buộc

• \(1\le N\le 200\,000\).
• \(0\le H\le N\).
• \(0\le A[i]\le 10^9\).
• \(B[i]\in\{0,1\}\).
• \(0\le L[i]\le R[i]\le N\).

Phân nhóm

Grader mẫu

Grader mẫu đọc N H, sau đó lần lượt đọc bốn mảng \(A,B,L,R\). Grader in \(T[0],\ldots,T[H]\) trên một dòng.

4 3
8 8 2 4
1 0 1 0
1 0 2 3
1 2 2 4

-1 20 14 -1

1 1
1000000000
0
1
1

1000000000 -1

7 3
4 7 0 3 8 4 5
0 0 0 0 0 0 0
0 0 0 1 0 1 2
5 1 2 5 5 6 3

7 -1 -1 -1

20 7
3 3 4 1 3 2 0 1 4 3 4 0 0 1 0 4 4 5 5 0
1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 1
0 0 1 1 2 1 2 2 1 1 0 1 1 3 2 2 1 6 4 4
3 2 3 3 6 2 2 4 3 4 4 5 3 6 6 5 7 8 8 9

-1 16 11 10 9 10 12 15

Nguồn: Kỳ thi tuyển chọn đội tuyển IOI Hàn Quốc 2026 - Vòng 2, giấy phép CC BY-NC-SA 4.0.