Đề bài

Youngwoo có hai mảng số nguyên \(A,B\) cùng độ dài \(N\), trong đó \(A[i]\le B[i]\) với mọi \(i\).

Một đoạn \([l,r]\) được gọi là tuyệt vời nếu có thể biến mảng

thành

bằng cách lặp lại thao tác sau. Với mảng hiện tại \(X=[X[0],\ldots,X[r-l]]\), chọn hai chỉ số phân biệt \(i,j\) sao cho \(X[i]=X[j]\), rồi tăng \(X[i]\) thêm \(1\).

Có \(Q\) truy vấn. Truy vấn thứ \(j\) hỏi đoạn \([L[j],R[j]]\) có tuyệt vời hay không.

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

vector<int> array_operation(
    vector<int> A,
    vector<int> B,
    vector<int> L,
    vector<int> R
);

Hàm phải trả về mảng \(S\) độ dài \(Q\). S[j] bằng \(1\) nếu đoạn được hỏi là tuyệt vời, ngược lại bằng \(0\). Hàm đượ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,Q\le 250\,000\).
• \(1\le A[i]\le B[i]\le 10^9\).
• \(0\le L[j]\le R[j]\le N-1\).

Phân nhóm

Grader mẫu

Grader mẫu đọc \(N,Q\), tiếp theo là \(N\) dòng A[i] B[i], rồi \(Q\) dòng L[j] R[j]. Grader in mảng kết quả trên một dòng.

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

1 1 0

5 5
1 2
2 3
1 1
2 4
1 2
0 2
0 4
1 3
1 4
2 3

1 1 0 1 0

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