Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#1327 · Truy vấn dãy

MÔ TẢ BÀI TOÁN

Cho một dãy A gồm N phần tử. Ban đầu, giá trị của các phần tử đều bằng 0. Có Q truy vấn, truy vấn thứ i được mô tả bởi hai số nguyên r_i và p_i, yêu cầu thực hiện p_i lần các thao tác sau:

  • Chọn phần tử có giá trị nhỏ nhất trong các phần tử có vị trí từ 1 đến r_i. Nếu có nhiều phần tử có cùng giá trị nhỏ nhất, chọn phần tử có vị trí nhỏ nhất trong số chúng.
  • Tăng giá trị của phần tử được chọn thêm 1.

Hãy cho biết giá trị các phần tử trong dãy A sau khi thực hiện Q truy vấn trên.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên N, Q, (1 \leq N, Q \leq 10^5) - số phần tử của dãy A và số truy vấn cần thực hiện.
  • Q dòng tiếp theo, mỗi dòng gồm hai số nguyên r_i và p_i, (1 \leq r_i \leq N, 1 \leq p_i \leq 9 \times 10^8) - mô tả truy vấn thứ i.

Dữ liệu ra

In ra N số nguyên lần lượt là giá trị các phần tử trong dãy A sau khi thực hiện Q truy vấn.

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
Nguyễn Tri Bão Thắng @25807700104
438 ms 2268 KB
2421 Bytes
23/12/2025
15:30
2
T
Nguyễn Tri Bão Thắng @2180601452
527 ms 2232 KB
2420 Bytes
30/06/2023
19:31
3
T
Nguyễn Tri Bão Thắng @2180601452
534 ms 2236 KB
2421 Bytes
03/07/2023
15:20
4
GV. Bùi Phú Khuyên @KBP0100298
1061 ms 6500 KB
2192 Bytes
29/06/2023
16:12
5
Lê Duy Hải @2280600799
1418 ms 4416 KB
2173 Bytes
15/04/2024
12:07

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

  • Trong ví dụ thứ nhất:

    • Sau khi thực hiện truy vấn 1, dãy A trở thành: [4, 4, 3, 0, 0, 0, 0, 0]
    • Sau khi thực hiện truy vấn 2, dãy A trở thành: [4, 4, 3, 2, 2, 1, 1, 1]
    • Sau khi thực hiện truy vấn 3, dãy A trở thành: [4, 4, 3, 3, 3, 2, 1, 1]

  • Trong ví dụ thứ hai:

    • Sau khi thực hiện truy vấn 1, dãy A trở thành: [1, 0, 0, 0, 0]
    • Sau khi thực hiện truy vấn 2, dãy A trở thành: [1, 1, 0, 0, 0]
    • Sau khi thực hiện truy vấn 3, dãy A trở thành: [1, 1, 1, 0, 0]
    • Sau khi thực hiện truy vấn 4, dãy A trở thành: [2, 1, 1, 0, 0]
    • Sau khi thực hiện truy vấn 5, dãy A trở thành: [2, 2, 1, 0, 0]
Viết code