| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P194SUMG - Dịch vòng của hoán vị |
Time limit: 2s
Cho một hoán vị p chiều dài n và mảng một chiều độ dài m bao gồm các số nguyên từ 1 đến n.
Có q truy vấn, mỗi truy vấn có dạng sau: “Lấy một dãy con của a bao gồm các phần tử từ vị trí l đên r, hỏi dãy con đó có chứa một đoạn con không liên tiếp là đoạn dịch vòng của hoán vị p hay không?”. Các bạn hãy tìm câu trả lời cho mỗi truy vấn nhé.
Biết:
Hoán vị chiều dài n là một chuỗi gồm n số nguyên sao cho mỗi số nguyên từ 1 đến n xuất hiện đúng một lần.
Một dịch vòng của hoán vị (p1, p2, …, pn) là một hoán vị (pi, pi+1, …, pn, p1, p2, …, pi-1) với i là số nguyên bất kỳ trong khoảng từ 1 đến n. Ví dụ hoán vị (1, 3, 2) có 3 dịch vòng là (1, 3, 2), (3, 2, 1), (2, 1, 3).
Input
Dòng đầu tiên bao gôm 3 số nguyên n, m, q (0 < n, m, q ≤ 2*105) – lần lượt là độ dài của hoán vị p, độ dài của dãy a, số lương các truy vấn.
Dòng tiếp theo chứa n số nguyên từ 1 đến n là các phần từ của hoán vị p, mỗi số nguyên xuất hiện chính xác một lần.
Dòng tiếp theo chứa m số nguyên từ 1 đến n là các phần từ của dãy a.
Trong q dòng tiếp theo, mỗi dòng chứa hai số nguyên l, r là giới hạn của dãy con lấy từ dãy a (1 ≤ l, r ≤ m).
Output
Một dòng duy nhất chứa một chuỗi nhị phân độ dài q, chữ cái thứ i là câu trả lời cho truy vấn thứ i. Mỗi chữ cái có giá trị 1 nếu chuỗi con lấy từ dãy a chứa một đoạn con không liên tiếp là dịch vòng của hoán vị p, 0 nếu ngược lại.
Example
Input
Output
3 6 3
2 1 3
1 2 3 1 2 3
1 5
2 6
3 5
110
| Được gửi lên bởi: | adm |
| Ngày: | 2019-08-10 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
