| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
DIVSEQQ - Chia đoạn |
Cho dãy A gồm N phần tử. Cho Q truy vấn dạng (u, v) tìm e nhỏ nhất sao cho từ e tới u có thể chia thành x (x <= v) đoạn liên tiếp sao cho mỗi đoạn có tổng <= M.
Input
Dòng đầu chứa N, Q, M (M <= 10^9 )
Dòng thứ 2 chứa N số biểu diễn dãy A. (0 <= Ai <= M)
Q dòng sau, dòng thứ i chứa 2 số u, v mô tả truy vấn thứ i. (0 < u <= N, 0 < v <= 10^9)
Output
Gồm Q dòng
Dòng thứ i chứa kết quả của truy vấn thứ i
Example
Input: 5 2 8
1 2 3 4 5
4 2
5 2 Output: 1
3
Subtask 1: (21 tests)
N, Q <= 2000
Subtask 2: (10 tests)
N, Q <= 100000.
| Được gửi lên bởi: | CoderPTNK1114 |
| Ngày: | 2013-08-07 |
| Thời gian chạy: | 0.200s-0.400s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
| Nguồn bài: | Sưu tầm |
hide comments
|
|||||
|
2013-08-08 15:40:01 CoderPTNK1114
Dạ vâng em đã sửa lại đề rồi ạ. |
|||||
|
2013-08-08 14:30:41 hiepsieunhan
bài này A[i] <= M nhưng A[i] >= bao nhiêu vậy ? Phải nói rõ chứ ? |
|||||
|
2013-08-08 06:09:40 CoderPTNK1114
Mình đã sửa lại đề. |
|||||
|
2013-08-08 02:46:41 Zịt Kon Kute
ở truy vấn đầu tiên: nếu e=1 thì từ 1 đến 4 có thể chia thành nhiều hơn 2 đoạn mà: ví dụ 3 đoạn: đ1: 1 2 đ2: 3 đ3: 4 hoặc 4 đoạn: đ1: 1 đ2: 2 đ3: 3 đ4: 4 |
|||||
RSS