Hướng dẫn giải của KS Câu 5: Đoạn thẳng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giả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.
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
Với mỗi đoạn ~i~ cần biết có đoạn ~j \ne i~ nằm trong nó (~l_i \le l_j, r_j \le r_i~) không, và có đoạn ~j \ne i~ bao nó không.
Sub 1: Thử mọi cặp — ~O(n^2)~, dùng khi ~n \le 1000~
Kiểm tra từng cặp đoạn ~(i, j)~ với ~i \ne j~. Nếu chỉ nộp sub này: đúng 6/6 test.
Sub 2: Sắp xếp và tiền tố, hậu tố — ~O(n \log n)~
Sắp xếp theo ~l~ tăng dần, ~r~ giảm dần. Đoạn đứng sau có ~r~ nhỏ nhất (hậu tố) thì chứa đoạn đứng trước; đoạn đứng trước có ~r~ lớn nhất (tiền tố) thì bao đoạn đứng sau. Các đoạn trùng nhau được xử lý riêng. Lưu ý (quy ước theo định nghĩa ~a \le c~, ~d \le b~): hai đoạn giống hệt nhau (cùng ~l, r~) chứa lẫn nhau, nên cả hai đều in 1 ở cả hai dòng. Nếu chỉ nộp sub này: đúng 6/6 test.
Chương trình hoàn chỉnh
Nếu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. 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;
int n;
vector<long long> L, R; // doan thu i: [L[i], R[i]]
// Sub 1: xet tung cap (i, j) — O(n^2), dung khi n <= 1000
void sub1() {
vector<int> c1(n, 0), c2(n, 0); // c1: doan i chua doan khac; c2: doan i bi chua
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (L[i] <= L[j] && R[j] <= R[i]) c1[i] = 1;
if (L[j] <= L[i] && R[i] <= R[j]) c2[i] = 1;
}
for (int i = 0; i < n; i++) cout << c1[i] << (i + 1 < n ? " " : "\n");
for (int i = 0; i < n; i++) cout << c2[i] << (i + 1 < n ? " " : "\n");
}
// Sub 2: sap xep theo (L tang, R giam). Khi do doan dung sau p va co R <= R[p] se chua p (L lon hon),
// doan dung truoc p va co R >= R[p] se bao p (L nho hon). Cac doan trung nhau duoc xu ly rieng.
void sub2() {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
if (L[x] != L[y]) return L[x] < L[y];
return R[x] > R[y];
});
const long long INF = LLONG_MAX / 4;
vector<long long> suf(n + 1, INF); // suf[p] = min R tu vi tri p tro di
for (int p = n - 1; p >= 0; p--) suf[p] = min(suf[p + 1], R[ord[p]]);
vector<int> c1(n, 0), c2(n, 0);
long long premax = -INF; // max R tren cac vi tri truoc p
for (int p = 0; p < n; p++) {
int i = ord[p];
bool dup = (p > 0 && L[ord[p - 1]] == L[i] && R[ord[p - 1]] == R[i]) ||
(p + 1 < n && L[ord[p + 1]] == L[i] && R[ord[p + 1]] == R[i]);
c1[i] = (suf[p + 1] <= R[i]) || dup;
c2[i] = (premax >= R[i]) || dup;
premax = max(premax, R[i]);
}
for (int i = 0; i < n; i++) cout << c1[i] << (i + 1 < n ? " " : "\n");
for (int i = 0; i < n; i++) cout << c2[i] << (i + 1 < n ? " " : "\n");
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
L.assign(n, 0); R.assign(n, 0);
for (int i = 0; i < n; i++) cin >> L[i] >> R[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận