Submission #1244913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244913		CrabCNH	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	542 ms	74896 KiB

matryoshka

#include <bits/stdc++.h>

#define int long long
#define pii pair <int, int>
#define fi first
#define se second

using namespace std;

const int maxN = 4e5 + 5;
const int inf = 1e18 + 7;

struct ST {
    struct Node {
        int mi, sum;
    };

    vector <Node> st;
    vector <int> cnt;

    inline void init (int _n) {
        st.resize (_n * 4, {inf, 0});
        cnt.resize (_n, 0);
    }

    inline Node merge (Node A, Node B) {
        Node c = {min (A.mi, B.mi), A.sum + B.sum};
        return c;
    }

    void upd (int id, int l, int r, int pos, int val) {
        if (pos < l || pos > r)  {
            return;
        }
        if (l == r) {
            cnt[pos] += val;
            st[id].sum += val;
            st[id].mi = (cnt[pos] > 0 ? pos : inf);
            return;
        }
        int mid = (l + r) >> 1;
        upd (id * 2, l, mid, pos, val);
        upd (id * 2 + 1, mid + 1, r, pos, val);
        st[id] = merge (st[id * 2], st[id * 2 + 1]);
    }

    Node get (int id, int l, int r, int u, int v) {
        if (v < l || u > r) {
            return {inf, 0};
        }
        if (u <= l && r <= v) {
            return st[id];
        }
        int mid = (l + r) >> 1;
        Node tL = get (id * 2, l, mid, u, v);
        Node tR = get (id * 2 + 1, mid + 1, r, u, v);
        return merge (tL, tR);
    }
};

int n, q;
pii doll[maxN]; // r, h
vector <pii> off[maxN];
vector <int> pack[maxN];
vector <pii> all;
int res[maxN];
ST T;

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> q;
    vector <int> zip1, zip2;
    for (int i = 1; i <= n; i ++) {
        int x, y;
        cin >> x >> y;
        doll[i] = {x, y};
        zip1.push_back (x);
        zip2.push_back (y);
    }
    for (int i = 1; i <= q; i ++) {
        int a, b;
        cin >> a >> b;
        zip1.push_back (a);
        zip2.push_back (b);
        all.push_back ({a, b});
    }
    sort (zip1.begin (), zip1.end ());
    zip1.erase (unique (zip1.begin (), zip1.end ()), zip1.end ());
    sort (zip2.begin (), zip2.end ());
    zip2.erase (unique (zip2.begin (), zip2.end ()), zip2.end ());
    for (int i = 1; i <= n; i ++) {
        auto it1 = lower_bound (zip1.begin (), zip1.end (), doll[i].fi) - zip1.begin () + 1;
        auto it2 = lower_bound (zip2.begin (), zip2.end (), doll[i].se) - zip2.begin () + 1;
        doll[i] = {it1, it2};
        pack[it1].push_back (it2);
    }
    for (int i = 1; i <= q; i ++) {
        auto a = lower_bound (zip1.begin (), zip1.end (), all[i - 1].fi) - zip1.begin () + 1;
        auto b = lower_bound (zip2.begin (), zip2.end (), all[i - 1].se) - zip2.begin () + 1;
        off[a].push_back ({b, i});
    }
    int lim = zip2.size () + 2;
    T.init (lim);
    for (int cur = zip1.size (); cur >= 1; cur --) {
        for (auto it : pack[cur]) {
            auto [mi, sum] = T.get (1, 1, lim, it + 1, lim); // tim xem co con nao ghep duoc ko co thi ghep
            if (mi != inf) {
                T.upd (1, 1, lim, mi, -1); // ghep duoc roi thi xoa con day di roi lap no vao con moi
            }
        }
        for (auto it : pack[cur]) {
            T.upd (1, 1, lim, it, 1); // upd con moi vao
        }
        for (auto [it, id] : off[cur]) {
            res[id] = T.get (1, 1, lim, 1, it).sum;
        }
    }
    for (int i = 1; i <= q; i ++) {
        cout << res[i] << '\n';
    }
}

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