Submission #1216829

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216829		duckindog	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	358 ms	29436 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, q;
int r[N], h[N];

vector<int> saveD[N];
vector<pair<int, int>> saveQ[N];

const int MAX = 1'000'000;
namespace IT { 
    int cnt[N];
    int f[N << 2], g[N << 2];

    void build(int s, int l, int r) { 
        f[s] = MAX;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(s << 1, l, mid);
        build(s << 1 | 1, mid + 1, r);
    }
    void update(int s, int l, int r, int p, int x) { 
        if (l == r) { 
            cnt[p] += x;
            f[s] = (cnt[p] ? p : MAX);
            g[s] += x;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(s << 1, l, mid, p, x);
        else update(s << 1 | 1, mid + 1, r, p, x);
        f[s] = min(f[s << 1], f[s << 1 | 1]);
        g[s] = g[s << 1] + g[s << 1 | 1];
    }
    int query0(int s, int l, int r, int u, int v) { 
        if (v < l || u > r) return MAX;
        if (u <= l && r <= v) return f[s];
        int mid = (l + r) >> 1;
        return min(query0(s << 1, l, mid, u, v), query0(s << 1 | 1, mid + 1, r, u, v));
    } 
    int query1(int s, int l, int r, int u, int v) { 
        if (v < l || u > r) return 0;
        if (u <= l && r <= v) return g[s];
        int mid = (l + r) >> 1;
        return query1(s << 1, l, mid, u, v) + query1(s << 1 | 1, mid + 1, r, u, v);
    } 
}

int answer[N];

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

    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> r[i] >> h[i];

    vector<int> allR(r + 1, r + n + 1),
                allH(h + 1, h + n + 1);
    { // discrete
        sort(allR.begin(), allR.end());
        allR.erase(unique(allR.begin(), allR.end()), allR.end());

        sort(allH.begin(), allH.end());
        allH.erase(unique(allH.begin(), allH.end()), allH.end());

        for (int i = 1; i <= n; ++i) { 
            r[i] = upper_bound(allR.begin(), allR.end(), r[i]) - allR.begin();
            h[i] = upper_bound(allH.begin(), allH.end(), h[i]) - allH.begin();

            saveD[r[i]].push_back(h[i]);
        }
    }

    for (int i = 1; i <= q; ++i) { 
        int a, b; cin >> a >> b;
        a = lower_bound(allR.begin(), allR.end(), a) - allR.begin() + 1;
        b = upper_bound(allH.begin(), allH.end(), b) - allH.begin();

        saveQ[a].push_back({b, i});
    }
    
    const int sz = allH.size();
    IT::build(1, 1, sz);
    for (int i = allR.size(); i >= 1; --i) { 
        for (const auto& x : saveD[i]) { 
            int p = IT::query0(1, 1, sz, x + 1, sz);
            if (p != MAX) IT::update(1, 1, sz, p, -1);
        }
        for (const auto& x : saveD[i])
            IT::update(1, 1, sz, x, 1);

        for (const auto& [x, idx] : saveQ[i]) { 
            answer[idx] = IT::query1(1, 1, sz, 1, x);
        }
    }

    for (int i = 1; i <= q; ++i) cout << answer[i] << "\n";
}

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