Hướng dẫn giải của Trò chơi
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có k đoạn [li, ri] là các lượt tham gia trò chơi, cần với mỗi học sinh bj đếm số đoạn chứa bj. Đây là bài đếm điểm phủ, n có thể lên tới 10^9 nên không thể tạo mảng cho mọi học sinh.
Sub 1: Vét cạn — ~O(k \cdot q)~, dùng khi k, q \le 1000
Với mỗi học sinh b, duyệt mọi đoạn và đếm đoạn có li \le b \le ri. Nếu chỉ nộp sub này: đúng 8/20 test (12 test còn lại chạy quá giờ).
Sub 2: Mảng hiệu — ~O(n + k + q)~, dùng khi n \le 10^6
Cộng 1 tại li và trừ 1 tại ri + 1 vào mảng hiệu, lấy tổng tiền tố ta được số đoạn chứa mỗi học sinh. Nếu chỉ nộp sub này: đúng 13/20 test (7 test có n lớn hơn 10^6 chạy sai miền).
Sub 3 (đầy đủ): Sắp xếp và tìm kiếm nhị phân — ~O((k + q) \log k)~
Với mỗi b: số đoạn chứa b = (số đoạn có l \le b) - (số đoạn có r < b). Lý do: mọi đoạn có r < b đều có l \le r < b nên đã nằm trong nhóm thứ nhất. Sắp xếp riêng dãy l và dãy r, dùng upper_bound và lower_bound để đếm.
Bẫy: n có thể tới 10^9, dùng long long cho chỉ số và giá trị.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc n, k, q, các đoạn và các học sinh. Nếu k, q \le 1000 gọi sub1; nếu n \le 10^6 gọi sub2; còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long n, k, q;
vector<long long> L, R; // doan tham gia cua tro choi thu i: [L[i], R[i]]
vector<long long> B; // cac hoc sinh can hoi
// Sub 1: vet can O(k * q) - voi moi hoc sinh b, dem so doan chua b. Dung khi k, q <= 1000.
void sub1() {
for (long long b : B) {
long long cnt = 0;
for (int i = 0; i < k; i++)
if (L[i] <= b && b <= R[i]) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: mang hieu O(n + k + q) - danh dau tren ca hang n hoc sinh, lay tong tien to. Dung khi n <= 10^6.
void sub2() {
vector<long long> diff(n + 2, 0);
for (int i = 0; i < k; i++) {
diff[L[i]]++;
diff[R[i] + 1]--;
}
vector<long long> cnt(n + 2, 0);
long long run = 0;
for (long long x = 1; x <= n; x++) {
run += diff[x];
cnt[x] = run;
}
for (long long b : B) cout << cnt[b] << "\n";
}
// Sub 3: day du O(k log k + q log k).
// So doan chua b = (so doan co l <= b) - (so doan co r < b), vi moi doan co l <= r.
void sub3() {
vector<long long> Ls = L, Rs = R;
sort(Ls.begin(), Ls.end());
sort(Rs.begin(), Rs.end());
for (long long b : B) {
long long a = upper_bound(Ls.begin(), Ls.end(), b) - Ls.begin(); // l <= b
long long c = lower_bound(Rs.begin(), Rs.end(), b) - Rs.begin(); // r < b
cout << a - c << "\n";
}
}
int main() {
freopen("Trochoi.inp", "r", stdin);
freopen("Trochoi.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k >> q;
L.resize(k);
R.resize(k);
for (int i = 0; i < k; i++) cin >> L[i] >> R[i];
B.resize(q);
for (auto &x : B) cin >> x;
if (k <= 1000 && q <= 1000) sub1(); // du lieu nho: dem truc tiep
else if (n <= 1000000) sub2(); // n vua: mang hieu
else sub3();
return 0;
}
Bình luận