Thi đấu cầu lông (THTC Vòng Khu vực 2021)

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Tham gia đại hội thể thao toàn Thiên hà, đội Trái đất có \(n\) vận động viên tham gia bộ môn cầu lông. Vận động viên thứ \(i\) \((1 \le i \le n)\) có chỉ số thể lực là \(a_i\) và chỉ số kĩ thuật là \(b_i\). Theo thông tin thu nhận được, có \(m (n \le m)\) vận động viên của hành tinh \(Z\) cũng tham gia bộ môn cầu lông, vận động viên thứ \(j (1 \le j \le m)\) có chỉ số thể lực và kĩ thuật tương ứng là \(x_j, y_j\). Đội hành tinh \(Z\) sẽ cử \(n\) vận động viên, gồm các vận động viên liên tiếp từ vận động viên thứ \(k\) đến vận động viên thứ \(k + n - 1\) để đấu với \(n\) vận động viên của đội Trái đất và sẽ thi đấu đúng trận đấu \(n\) (mỗi vận động viên thi đấu một trận). Nếu vận động viên thứ \(i\) của đội Trái đất muốn chắc chắn thắng vận động viên thứ \(j\) của đội hành tinh \(Z\) thì \(a_i > x_j\)\(b_i > y_j\). Đội Trái đất muốn lên phương án sắp xếp các vận động viên tương ứng thi đấu với vận động viên được cử của đội hành tinh \(Z\) để có nhiều trận
chắc chắn thắng nhất.

Yêu cầu: Cho thông tin về \(n\) vận động viên của đội Trái đất, thông tin \(m\) vận động viên của đội hành tinh \(Z\)\(Q\) khả năng cử vận động viên bắt đầu từ các vận động viên \(k_1, k_2, ..., k_Q\), với mỗi khả năng cử vận động viên của hành tinh \(Z\), hãy giúp đội Trái đất lên phương án sắp xếp các vận động viên để có nhiều trận chắc chắn thắng nhất.

Input

Vào từ thiết bị vào chuẩn:

  • Dòng thứ nhất chứa ba số nguyên dương \(n, m, Q(m \le 10^5; Q \le 100)\);
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n (a_i \le 10^9\) với \(1 \le i \le n)\);
  • Dòng thứ ba chứa \(n\) số nguyên dương \(b_1, b_2, ..., b_n (b_i \le 10^9\) với \(1 \le i \le n)\);
  • Dòng thứ tư chứa \(m\) số nguyên dương \(x_1, x_2, ..., x_m (x_j \le 10^9\) với \(1 \le j \le m)\);
  • Dòng thứ năm chứa \(m\) số nguyên dương \(y_1, y_2, ..., y_m (y_j \le 10^9\) với \(1 \le j \le m)\);
  • Dòng cuối chứa \(Q\) số nguyên dương \(k_1, k_2, ..., k_Q(1 \le k_t \le k_t + n - 1 \le m\) với \(1 \le t \le Q)\) .

Output

  • Ghi ra thiết bị ra chuẩn gồm \(Q\) dòng, mỗi dòng một số nguyên là số trận chắc chắn thắng lần lượt tương ứng với \(Q\) khả năng cử vận động viên của đội hành tinh \(Z\) trong dữ liệu vào.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(n \le 6\);
  • Subtask \(2\) (\(25\%\) số điểm): \(n \le 100\);
  • Subtask \(3\) (\(25\%\) số điểm): \(n \le 5000\);
  • Subtask \(4\) (\(25\%\) số điểm): \(n \le 30000\);

Example

Test 1

Input
3 6 4
10 20 30
10 20 30
10 20 30 40 50 60
10 20 30 40 50 60
1 2 3 4
Output
2
1
0
0

Bình luận

Không có bình luận nào.