Nhà thực vật học Hazel đến tham quan một triển lãm đặc biệt tại Vườn Bách thảo Singapore. Trong triển lãm, \(n\) cây có chiều cao đôi một khác nhau được đặt trên một vòng tròn. Các cây được gán nhãn từ \(0\) đến \(n-1\) theo chiều kim đồng hồ, với cây \(n-1\) nằm bên cạnh cây \(0\).

Với mỗi cây \(i\) (\(0 \le i \le n-1\)), Hazel so sánh cây \(i\) với từng cây trong \(k-1\) cây kế tiếp theo chiều kim đồng hồ, rồi ghi lại số \(r[i]\) là số cây cao hơn cây \(i\) trong số \(k-1\) cây đó. Như vậy, mỗi giá trị \(r[i]\) phụ thuộc vào tương quan chiều cao của một số cây liên tiếp.

Ví dụ, giả sử \(n=5\), \(k=3\) và \(i=3\). Khi đó, \(k-1=2\) cây kế tiếp theo chiều kim đồng hồ tính từ cây \(i=3\) là cây \(4\) và cây \(0\). Nếu cây \(4\) cao hơn cây \(3\) và cây \(0\) thấp hơn cây \(3\), Hazel sẽ ghi lại \(r[3]=1\).

Bạn có thể giả sử Hazel đã ghi các giá trị \(r[i]\) chính xác. Do đó, tồn tại ít nhất một cách gán các chiều cao đôi một khác nhau cho các cây phù hợp với những giá trị này.

Bạn được yêu cầu so sánh chiều cao của \(q\) cặp cây. Đáng tiếc, bạn không thể đến triển lãm. Nguồn thông tin duy nhất của bạn là sổ ghi chép của Hazel, chứa giá trị \(k\) và dãy \(r[0],\ldots,r[n-1]\).

Với mỗi cặp cây khác nhau \(x\) và \(y\) cần so sánh, hãy xác định trường hợp nào trong ba trường hợp sau xảy ra:

• Cây \(x\) chắc chắn cao hơn cây \(y\): với mọi cách gán chiều cao đôi một khác nhau \(h[0],\ldots,h[n-1]\) phù hợp với mảng \(r\), luôn có \(h[x]>h[y]\).
• Cây \(x\) chắc chắn thấp hơn cây \(y\): với mọi cách gán chiều cao đôi một khác nhau \(h[0],\ldots,h[n-1]\) phù hợp với mảng \(r\), luôn có \(h[x]<h[y]\).
• Không thể kết luận: không thuộc trường hợp nào trong hai trường hợp trên.

Chi tiết cài đặt

Bạn cần cài đặt các hàm C++ sau:

void init(int k, std::vector<int> r);

• \(k\): số cây liên tiếp có chiều cao quyết định mỗi giá trị \(r[i]\).
• \(r\): mảng kích thước \(n\), trong đó \(r[i]\) là số cây cao hơn cây \(i\) trong \(k-1\) cây kế tiếp theo chiều kim đồng hồ.
• Hàm này được gọi đúng một lần, trước mọi lời gọi compare_plants.

int compare_plants(int x, int y);

• \(x\), \(y\): nhãn của hai cây cần so sánh.
• Hàm phải trả về \(1\) nếu cây \(x\) chắc chắn cao hơn cây \(y\); \(-1\) nếu cây \(x\) chắc chắn thấp hơn cây \(y\); \(0\) nếu không thể kết luận.
• Hàm này được gọi đúng \(q\) lần.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n k q.
• Dòng \(2\): r[0] r[1] ... r[n-1].
• Dòng \(3+i\) (\(0 \le i \le q-1\)): x y cho lời gọi compare_plants thứ \(i\) (đánh số từ \(0\)).

Dữ liệu ra

Trình chấm mẫu in trên dòng \(1+i\) (\(0 \le i \le q-1\)) giá trị trả về của lời gọi compare_plants thứ \(i\).

Ràng buộc

• \(2 \le k \le n \le 200\,000\).
• \(1 \le q \le 200\,000\).
• \(0 \le r[i] \le k-1\) (\(0 \le i \le n-1\)).
• \(0 \le x < y \le n-1\).

Tồn tại ít nhất một cách gán các chiều cao đôi một khác nhau cho các cây phù hợp với mảng \(r\).

Phân nhóm

Ví dụ

init(3, [0, 1, 1, 2])

init(2, [0, 1, 0, 1])

Nguồn

IOI 2020, Ngày 1 — Comparing Plants (plants). Đề chính thức tiếng Anh và bản dịch tiếng Việt.