Submission #1189296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189296		Born_To_Laugh	Matryoshka (JOI16_matryoshka)	C++17	0 / 100	0 ms	328 KiB

matryoshka

#include <bits/stdc++.h>
#define all(sth) sth.begin(), sth.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

class Fenwick_Tree {
private:
    int n;
    vector<int> bit;
public:
    Fenwick_Tree(int len) {
        n = len;
        bit.assign(n + 1, 0);
    }
    void Point_Update(int pos, int val) {
        for (; pos <= n; pos += pos & (-pos)) {
            bit[pos] = max(bit[pos], val);
        }
    }
    int get_max(int pos) {
        int ans = 0;
        for (; pos > 0; pos -= pos & (-pos)) {
            ans = max(ans, bit[pos]);
        }
        return ans;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<pair<int, int>> item(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> item[i].first >> item[i].second;
    }
    sort(item.begin() + 1, item.end(), [](pair<int, int> a, pair<int, int> b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });

    vector<array<int, 3>> query(q + 1);
    for (int i = 1; i <= q; ++i) {
        cin >> query[i][0] >> query[i][1];
        query[i][2] = i;
    }
    sort(query.begin() + 1, query.end(), [](array<int, 3> a, array<int, 3> b) {
        if (a[0] != b[0]) return a[0] > b[0];
        return a[1] < b[1];
    });

    vector<int> compress;
    for (int i = 1; i <= n; ++i) {
        compress.push_back(item[i].second);
        compress.push_back(item[i].second - 1);
    }
    for (int i = 1; i <= q; ++i) {
        compress.push_back(query[i][1]);
    }
    sort(all(compress));
    compress.erase(unique(all(compress)), compress.end());
    auto get_pos = [&](int val) {
        return upper_bound(all(compress), val) - compress.begin();
    };

    Fenwick_Tree ft(compress.size() + 10);
    vector<int> ans(q + 1, 0);
    int j = 1;
    for (int i = 1; i <= q; ++i) {
        while (j <= n && item[j].first >= query[i][0]) {
            int y = item[j].second;
            int pos_y_minus_1 = upper_bound(all(compress), y - 1) - compress.begin();
            int current_max = ft.get_max(pos_y_minus_1) + 1;
            int pos_y = upper_bound(all(compress), y) - compress.begin();
            ft.Point_Update(pos_y, current_max);
            j++;
        }
        int query_pos = get_pos(query[i][1]);
        ans[query[i][2]] = ft.get_max(query_pos);
    }
    for (int i = 1; i <= q; ++i) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 49