1. Tóm tắt đề bài

Cho ~N~ danh sách số nguyên. Dòng thứ ~i~ bắt đầu bằng số nguyên ~K_i~ biểu thị số lượng phần tử của dòng đó, theo sau là ~K_i~ số nguyên. Có ~Q~ truy vấn, mỗi truy vấn gồm hai số ~r~ và ~c~: hãy in ra giá trị ở hàng ~r~, cột thứ ~c~ (chỉ số hàng và cột tính từ 1). Nếu vị trí đó không tồn tại (~c > K_r~), in ra -1.

• Dữ liệu vào (Input):

  • Dòng 1: Hai số nguyên ~N, Q~ (~N, Q \le 2 \times 10^5~).
  • ~N~ dòng tiếp theo: Dòng thứ ~i~ ghi số ~K_i~ và theo sau là ~K_i~ số nguyên (~\sum K_i \le 5 \times 10^5~).
  • ~Q~ dòng tiếp theo: Mỗi dòng gồm 2 số nguyên ~r, c~.

• Dữ liệu ra (Output):

  • Gồm ~Q~ dòng tương ứng với kết quả của mỗi truy vấn.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:

  • ~N, Q \le 2 \times 10^5~.
  • Tổng số phần tử của toàn bộ ma trận: ~\sum K_i \le 5 \times 10^5~.
  • Số lượng truy vấn ~Q~ lớn (~2 \times 10^5~), đòi hỏi mỗi truy vấn phải trả lời ngay trong thời gian ~\mathcal{O}(1)~.

• Bẫy bộ nhớ khi dùng mảng hai chiều tĩnh:

  • Nếu khai báo mảng tĩnh dạng int a[200005][200005], chương trình sẽ tốn ~\approx 2 \times 10^5 \times 2 \times 10^5 \times 4~ bytes ~\approx 160.000\text{ MB} = 160\text{ GB}~ bộ nhớ ~\rightarrow~ Tràn bộ nhớ ngay lập tức (Memory Limit Exceeded).
  • Mặc dù số hàng ~N~ có thể lớn, nhưng tổng số phần tử thực tế chỉ có ~\sum K_i \le 5 \times 10^5~. Đây chính là dạng ma trận răng cưa (mỗi hàng có độ dài khác nhau).
  • Giải pháp tối ưu: Dùng mảng động các vector (vector<int> a[N + 1]), mỗi hàng chỉ cấp phát đúng số phần tử mà nó chứa.

• Tối ưu vào/ra:

  • Do số lượng dữ liệu vào/ra lên tới hàng trăm nghìn số (~N, Q \le 2 \times 10^5~), bắt buộc phải mở tốc độ nhập xuất chuẩn bằng cin.tie(NULL);.

3. Thuật toán xử lý

• Cấu trúc lưu trữ:

  • Khai báo một mảng các vector số nguyên toàn cục: vector<int> bang[NMAX].
  • Hàng thứ ~i~ sẽ lưu các phần tử theo thứ tự nhập vào. Vì vector trong C++ đánh số chỉ số từ 0, ta có thể:
    • Hoặc đẩy thêm một phần tử giả 0 vào đầu mỗi hàng để chỉ số cột bắt đầu từ 1.
    • Hoặc truy xuất cột ~c~ tại vị trí c - 1.

• Các bước thực hiện:

  1. Nhập ~N~ và ~Q~.
  2. Với mỗi dòng ~i~ từ ~1~ đến ~N~:
     • Nhập số lượng phần tử ~K_i~ của dòng đó.
     • Cho một vòng lặp chạy ~K_i~ lần: đọc từng giá trị và dùng lệnh push_back để thêm vào bang[i].
  3. Lần lượt xử lý ~Q~ truy vấn:
     • Đọc tọa độ hàng ~r~ và cột ~c~.
     • Kiểm tra tính hợp lệ của vị trí:
       • Nếu ~c > bang[r].size()~ (cột vượt quá số lượng phần tử thực có của hàng ~r~): in ra -1.
       • Ngược lại: in ra phần tử bang[r][c - 1].
     • Xuống dòng bằng cout << endl;.

• Độ phức tạp:

  • Thời gian:
    • Nhập dữ liệu ma trận: ~\mathcal{O}(N + \sum K_i)~.
    • Trả lời mỗi truy vấn: ~\mathcal{O}(1)~.
    • Tổng thời gian: ~\mathcal{O}(N + \sum K_i + Q) \approx 10^6~ phép tính, chạy cực nhanh trong thời gian ~< 0.1~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(N + \sum K_i)~, tiêu tốn chưa đến ~15\text{ MB}~, hoàn toàn tối ưu.

4. Mã nguồn cài đặt (C++)

#include <bits/stdc++.h>
using namespace std;

const int NM = 200005;

// Mảng vector lưu ma trận răng cưa động
vector<int> a[NM];

int main() {
    // Tối ưu tốc độ nhập/xuất chuẩn
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    // Nhập dữ liệu cho từng hàng của ma trận
    for (int i = 1; i <= n; i++) 
    {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) 
        {
            int x;
            cin >> x;
            a[i].push_back(x);
        }
    }

    // Xử lý lần lượt từng truy vấn
    for (int i = 1; i <= q; i++) 
    {
        int r, c;
        cin >> r >> c;

        // Kiểm tra xem vị trí cột c có nằm trong phạm vi số phần tử của hàng r không
        if (c > a[r].size()) 
        {
            cout << -1 << endl;
        } else 
        {
            // Do vector đánh chỉ số từ 0 nên cột thứ c nằm ở vị trí c - 1
            cout << a[r][c - 1] << endl;
        }
    }

    return 0;
}