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ủ

#1049 · Truy vấn dãy số

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 105) - 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.

Subtask:

  • Subtask 1 (10% số điểm): N, Q \leq 2000, p_i = 1
  • Subtask 2 (25% số điểm): N, Q \leq 2000
  • Subtask 3 (25% số điểm): p_i = 1
  • Subtask 4 (40% số điểm): Không có ràng buộc gì thêm

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

# Tài khoản Kết suất Lúc nộp
1
K
Trần Kim Khoa @2410060173
310 ms 312 KB
6404 Bytes
14/08/2025
14:56
2
T
Nguyễn Trung Tuyến @2011064511
571 ms 9688 KB
4737 Bytes
13/09/2025
21:07
3
H
Clb Olympic Tin Học Hutech @olympictinhoc
1071 ms 6504 KB
2190 Bytes
26/11/2022
15:16
4
T
Nguyễn Tri Bão Thắng @2180601452
1071 ms 6508 KB
2971 Bytes
27/11/2022
12:35
5
H
Clb Olympic Tin Học Hutech @olympictinhoc
1084 ms 6516 KB
2190 Bytes
26/11/2022
15:22
6
Nguyễn Tri Bão Thắng @25807700104
1109 ms 6528 KB
2870 Bytes
23/12/2025
13:27
7
T
Nguyễn Trung Tuyến @2011064511
1212 ms 35388 KB
6635 Bytes
13/09/2025
21:06
8
Lê Duy Hải @2280600799
1352 ms 4412 KB
2188 Bytes
12/08/2025
09:42
9
Lê Duy Hải @2280600799
1356 ms 4412 KB
2188 Bytes
12/08/2025
09:41
10
Lê Duy Hải @2280600799
1356 ms 4412 KB
2188 Bytes
12/08/2025
09:42
11
Lê Duy Hải @2280600799
1448 ms 4416 KB
2188 Bytes
15/04/2024
12:06
12
K
Trần Kim Khoa @2410060173
2171 ms 1088 KB
1726 Bytes
14/08/2025
13:53
13
K
Trần Kim Khoa @2410060173
2216 ms 1060 KB
1832 Bytes
13/08/2025
17:08

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