Submission #1189299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189299		Born_To_Laugh	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	171 ms	11556 KiB

matryoshka

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

// no need to make ll = int
static const ll INF = (ll)1e18;

struct Fenwick {
    int n;
    vector<ll> f;
    Fenwick(int _n): n(_n), f(n+1, 0) {}
    // point‑update to take the maximum
    void update(int i, ll v) {
        for (; i <= n; i += i & -i)
            f[i] = max(f[i], v);
    }
    // prefix maximum on [1..i]
    ll query(int i) {
        ll r = 0;                   // start at 0, not –INF
        for (; i > 0; i -= i & -i)
            r = max(r, f[i]);
        return r;
    }
};

void solve(){
    int n, q;
    cin >> n >> q;
    vector<pair<int,int>> item(n);
    for(int i = 0; i < n; i++)
        cin >> item[i].first >> item[i].second;

    // sort by descending radius, tie‑break ascending height
    sort(item.begin(), item.end(),
         [](auto &A, auto &B){
             if (A.first != B.first) return A.first > B.first;
             return A.second < B.second;
         });

    vector<array<int,3>> qry(q);
    for(int i = 0; i < q; i++){
        cin >> qry[i][0] >> qry[i][1];
        qry[i][2] = i;
    }
    // sort queries by the same ordering on radius
    sort(qry.begin(), qry.end(),
         [](auto &A, auto &B){
             if (A[0] != B[0]) return A[0] > B[0];
             return A[1] < B[1];
         });

    // compress *only* heights (no need for h‑1)
    vector<int> coord;
    coord.reserve(n + q);
    for(auto &it: item)     coord.push_back(it.second);
    for(auto &it: qry)      coord.push_back(it[1]);
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    auto get_pos = [&](int x){
        return int(lower_bound(coord.begin(), coord.end(), x) - coord.begin()) + 1;
    };

    Fenwick ft((int)coord.size());
    vector<ll> ans(q);
    int j = 0;
    for(auto &Q: qry){
        int R = Q[0], H = Q[1], idx = Q[2];
        // bring in all items with r >= R
        while (j < n && item[j].first >= R) {
            int hpos = get_pos(item[j].second);
            // *** allow non‑decreasing chain ***
            ll best = ft.query(hpos) + 1;
            ft.update(hpos, best);
            j++;
        }
        ans[idx] = ft.query(get_pos(H));
    }

    for(ll x: ans)
        cout << x << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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