| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
YPKTH - Phần tử thứ K |
Cho dãy số A có N phần tử nguyên phân biệt.
Cho Q truy vấn, mỗi truy vấn có dạng: L R K
Yêu cầu: mỗi truy vấn xuất ra phần tử lớn thứ K sau khi sắp xếp các phần tử AL, AL+1, …, AR theo thứ tự tăng dần.
Giới hạn:
1 ≤ N, Q ≤ 105
|Ai| ≤ 109 với 1 ≤ i ≤ N
1 ≤ L ≤ R ≤ N
1 ≤ K ≤ R-L+1
Input:
- Dòng đầu tiên chứa số N.
- Dòng tiếp theo chứa N số A1, A2, …, AN.
- Dòng tiếp theo chứa số Q.
- Q dòng tiếp theo, mỗi dòng chứa 3 số L, R, K.
Output:
Q dòng, mỗi dòng chứa câu trả lời cho một truy vấn theo thứ tự nhập vào.
Ví dụ:
|
Input |
Output |
|
7 2 1 5 4 3 6 8 4 1 2 2 3 7 4 4 6 2 5 5 1
|
2 6 4 3 |
| Được gửi lên bởi: | Yen Vu |
| Ngày: | 2013-09-07 |
| Thời gian chạy: | 1s-3s |
| 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 |
hide comments
|
||||||
|
2017-10-05 16:14:00
IT + boobssort = 1 đấm AC |
||||||
|
2017-07-22 01:37:35
PIT nlogn |
||||||
|
2017-02-15 14:21:32
có thánh nào trâu ko ạ |
||||||
|
2016-11-27 16:58:39 Nguyễn Hữu Phong
Mergesort + discretize + bs + bit + Mo' function, tính ra còn hơn nlogn^2 nữa, nhưng cũng AC |
||||||
|
2016-07-09 13:39:21 Trần Quang Anh
bài này dùng Persistent IT nhé |
||||||
|
2016-06-28 15:23:28
IT(sort) chịu không nổi mảng :(( |
||||||
|
2016-06-07 17:29:48
Sự khác biệt giữa lower_bound và upper_bound @@ |
||||||
|
2016-05-29 14:08:58
vler minhsn |
||||||
|
2016-03-11 14:27:09 LeGoLas
minhsn chem gio kinh wa,chua AC ma da chem rui |
||||||
|
2015-11-21 03:36:54 minhsn
QHD bao loi + splay tree + LCA +tarjan |
||||||
RSS