Nhận thấy, ~2~ phát bắn của Lợi chắc chắn vào đầu mút của các tấm bia.

Do đó ta rời rạc hoá toạ độ về từ ~1~ đến ~2 \times n~ nhằm dễ cài đặt.

Subtask ~1~: ~O(n^3)~.

Ta duyệt trâu qua hai toạ độ và các tấm bia để tìm kết quả tối ưu.

Subtask ~2~:~O(n^3 / 32)~.

Ta chuẩn bị tập hợp các tấm bia chứa toạ độ ~x~ là ~S_x~. Lưu ~S_x~ dưới dạng ~std::bitset~. Khi ta duyệt hai toạ độ ~x, y~, ta dễ dàng tính được phần hợp của ~S_x~ và ~S_y~ trong ~O(\frac{n}{32})~.

Subtask ~3~: ~O(n \times \log(n))~.

Ta duyệt toạ độ nhỏ hơn. Giả sử là ~x~. Giả sử tập hợp đoạn không chứa ~x~ là ~S~. Bài toán trở thành tìm toạ độ tối ưu trong ~x + 1, x + 2, ..., 2 \times n~ mà có nhiều đoạn trong ~S~ chứa nó nhất.

Nếu ta nhìn nhận bài toán trên theo hướng kĩ thuật quét đường thì sẽ thấy đây là một bài cơ bản. Ta duy trì mảng ~a_i~ là số tấm bia chứa toạ độ ~i~ trong khi duyệt tăng dần giá trị ~x~. Khi xét đến ~x~ và tồn tại tấm bia ~[x, x']~. Ta biết chắc rằng: ~a[x..x']~ giảm đi ~1~. Việc đơn giản bây giờ là cập nhật lại mảng ~a~ và lấy ~max(a[(x+1)..(2 \times n)])~.

Do đó mảng ~a~ của ta cần hỗ trợ hai thao tác:

• Giảm các giá trị trong một đoạn
• Lấy giá trị max trong một đoạn.

Vậy ta dùng CTDL Segment tree để tối ưu.

Code mẫu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;

struct Segtree {
    int n;
    vector<int> tree, lazy;

    Segtree(int _n) : n(_n) {
        tree.assign(n * 4 + 5, 0);
        lazy.assign(n * 4 + 5, 0);
    }

    void build(int node, int l, int r, int* sum) {
        if (l == r) {
            tree[node] = sum[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(node * 2, l, mid, sum);
        build(node * 2 + 1, mid + 1, r, sum);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    void build(int* sum) {
        build(1, 1, n, sum);
    }

    void push(int node) {
        for (int i = node * 2; i <= node * 2 + 1; ++ i) {
            tree[i] -= lazy[node];
            lazy[i] += lazy[node];
        }
        lazy[node] = 0;
    }

    void update(int node, int l, int r, int u, int v) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            tree[node] -= 1;
            lazy[node] += 1;
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        update(node * 2, l, mid, u, v);
        update(node * 2 + 1, mid + 1, r, u, v);
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    void update(int l, int r) {
        update(1, 1, n, l, r);
    }

    int get(int node, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return tree[node];
        push(node);
        int mid = (l + r) >> 1;
        return max(get(node * 2, l, mid, u, v), get(node * 2 + 1, mid + 1, r, u, v));
    }

    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

int n;
pair<int, int> a[N];
vector<int> pos[N * 2];
int sum[N * 2];

void compress() {
    vector<int> vt;
    for (int i = 1; i <= n; ++ i) {
        auto& [u, v] = a[i];
        vt.push_back(u);
        vt.push_back(v);
    }
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    for (int i = 1; i <= n; ++ i) {
        auto& [u, v] = a[i];
        u = upper_bound(vt.begin(), vt.end(), u) - vt.begin();
        v = upper_bound(vt.begin(), vt.end(), v) - vt.begin();
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    compress();
    for (int i = 1; i <= n; ++ i) {
        auto [u, v] = a[i];
        // cout << u << " " << v << endl;
        pos[u].push_back(v);
        sum[u] ++;
        sum[v + 1] --;
    }
    int res = 0;
    for (int i = 1; i <= 2 * n; ++ i) {
        sum[i] += sum[i - 1];
        res = max(res, sum[i]);
    }
    Segtree sgt(n * 2);
    sgt.build(sum);
    for (int i = 1; i < 2 * n; ++ i) {
        for (auto j : pos[i]) {
            sgt.update(i, j);
        }
        // cout << i << " " << sum[i] << " " << sgt.get(i + 1, 2 * n) << endl;
        res = max(res, sum[i] + sgt.get(i + 1, 2 * n));
    }
    cout << res;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
}