Submission #1134810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134810		gyg	Examination (JOI19_examination)	C++20	2 / 100	3091 ms	26128 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

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';
}

arr<int, Q> ans;
vec<int> upd_lst;
void slv(vec<int>& qry_lst) {
    for (int i : qry_lst) 
        for (int j : upd_lst) 
            ans[i] += (a[j] >= a_rq[i] && b[j] >= b_rq[i]);
}

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_lst.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: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57