Submission #1134812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134812		gyg	Examination (JOI19_examination)	C++20	100 / 100	2886 ms	43280 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second 
#define lb lower_bound
#define pb push_back
const int N = 1e5 + 5, Q = 1e5 + 5;

int n, q, sq;
arr<int, N> a, b, c;
arr<int, Q> a_rq, b_rq, c_rq; // Note: this might exceed N - shouldn't matter tho

map<int, int> a_crd, b_crd;
vec<vec<int>> evnt;
void prcmp() {
    set<int> a_st, b_st;
    for (int i = 1; i <= n; i++) a_st.insert(a[i]), b_st.insert(b[i]);
    while (a_st.size()) {
        int x = *a_st.begin(); a_st.erase(a_st.begin());
        int id = a_crd.size() + 1;
        a_crd.insert({x, id});
    }
    while (b_st.size()) {
        int x = *b_st.begin(); b_st.erase(b_st.begin());
        int id = b_crd.size() + 1;
        b_crd.insert({x, id});
    }

    for (int i = 1; i <= n; i++) a[i] = a_crd[a[i]], b[i] = b_crd[b[i]];
    for (int i = 1; i <= q; i++) {
        a_rq[i] = (a_crd.lb(a_rq[i]) == a_crd.end()) ? n + 1 : a_crd.lb(a_rq[i])->sec;
        b_rq[i] = (b_crd.lb(b_rq[i]) == b_crd.end()) ? n + 1 : b_crd.lb(b_rq[i])->sec;
    }

    for (int i = 1; i <= n; i++) evnt.pb({c[i], 1, i});
    for (int i = 1; i <= q; i++) evnt.pb({c_rq[i], 0, i});
    sort(evnt.rbegin(), evnt.rend());

    // for (int i = 1; i <= n; i++) cout << a[i] << " " << b[i] << '\n';
    // cout << '\n';
    // for (int i = 1; i <= q; i++) cout << a_rq[i] << " " << b_rq[i] << '\n';
}

struct Sg {
    arr<int, 4 * N> sg;
    void intl() { sg.fill(0); }
    void upd(int i, int x, int u = 1, int lw = 1, int hg = n) {
        if (i < lw || hg < i) return;
        if (lw == hg) { sg[u] += x; return; }
        int md = (lw + hg) / 2;
        upd(i, x, 2 * u, lw, md), upd(i, x, 2 * u + 1, md + 1, hg);
        sg[u] = sg[2 * u] + sg[2 * u + 1];
    }
    int qry(int l, int r, int u = 1, int lw = 1, int hg = n) {
        if (l > r) return 0;
        if (r < lw || hg < l) return 0;
        if (l <= lw && hg <= r) return sg[u];
        int md = (lw + hg) / 2;
        return qry(l, r, 2 * u, lw, md) + qry(l, r, 2 * u + 1, md + 1, hg);
    }
} sg;

arr<int, Q> ans;
arr<vec<int>, N> upd_at, qry_at;
void slv(vec<int>& qry) {
    for (int i : qry) qry_at[a_rq[i]].push_back(i);

    sg.intl();
    for (int i = n; i >= 1; i--) {
        for (int j : upd_at[i]) sg.upd(b[j], +1);
        for (int j : qry_at[i]) ans[j] += sg.qry(b_rq[j], n);
    }

    for (int i : qry) qry_at[a_rq[i]].clear();
}

vec<int> upd, qry;
void cmp() {
    for (vec<int> x : evnt) {
        // cout << x[0] << " " << x[1] << " " << x[2] << ": " << endl;
        // for (int i : upd) cout << i << " "; 
        // cout << endl;
        // for (int i : qry) cout << i << " "; 
        // cout << endl;

        int id = x[2];
        if (x[1] == 1) {
            upd.pb(id);
            if (upd.size() >= sq) {
                slv(qry);
                for (int i : upd) upd_at[a[i]].pb(i);
                upd.clear(), qry.clear();
            }
        } else {
            for (int i : upd) ans[id] += (a[i] >= a_rq[id] && b[i] >= b_rq[id]);
            qry.pb(id);
        }
    }
    slv(qry);

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

signed main() {
    // freopen("in", "r", stdin);
    cin.sync_with_stdio(false), cin.tie(0);
    cin >> n >> q; sq = max((int) sqrtl(n), 1ll); // Change to 1300
    for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; c[i] = a[i] + b[i]; }
    for (int i = 1; i <= q; i++) { cin >> a_rq[i] >> b_rq[i] >> c_rq[i]; c_rq[i] = max(c_rq[i], a_rq[i] + b_rq[i]); }

    prcmp();
    cmp();
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57