Submission #1247089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247089		quannnguyen2009	Examination (JOI19_examination)	C++20	100 / 100	156 ms	25440 KiB

examination

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1e5+5, mod = 1e9+7, inf = 1e18;

int n, q;
int s[N], t[N], x[N], y[N], z[N], ans[N];

struct FenwickTree {
    int bit[4*N];

    int get(int p) {
        int idx = p, ans = 0;
        while (idx>0) {
            ans += bit[idx];
            idx -= (idx&(-idx));
        }
        return ans;
    }

    void upd(int u, int v) {
        int idx = u;
        while (idx<4*N) {
            bit[idx]+=v;
            idx+=(idx&(-idx));
        }
    }
} fw_x, fw_y;

struct Query {
    int s, x, y, t, i;
    bool operator<(const Query& o) const {
        if (s==o.s) return t>o.t;
        return s>o.s;
    }
};

vector<Query> qs;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    vector<int> v;
    for (int i=1; i<=n; i++) {
        cin >> s[i] >> t[i];
        v.pb(s[i]); v.pb(t[i]);
    }
    for (int i=1; i<=q; i++) {
        cin >> x[i] >> y[i] >> z[i];
        v.pb(x[i]); v.pb(y[i]);
        z[i] = max(z[i], x[i]+y[i]);
    }
    sort(all(v)); v.erase(unique(all(v)), v.end());
    for (int i=1; i<=q; i++) {
        x[i] = lower_bound(all(v), x[i])-v.begin()+1;
        y[i] = lower_bound(all(v), y[i])-v.begin()+1;
        qs.pb({z[i], x[i], y[i], 0, i});
    }
    for (int i=1; i<=n; i++) {
        int sum = s[i]+t[i];
        s[i] = lower_bound(all(v), s[i])-v.begin()+1;
        t[i] = lower_bound(all(v), t[i])-v.begin()+1;
        qs.pb({sum, s[i], t[i], 1, 0});
    }
    sort(all(qs));
    int cnt = 0;
    for (auto [s, x, y, t, i]: qs) {
        if (t==1) {
            fw_x.upd(x, 1);
            fw_y.upd(y, 1);
            cnt++;
        } else {
            ans[i] = cnt-fw_x.get(x-1)-fw_y.get(y-1);
        }
    }
    for (int i=1; i<=q; i++) cout << ans[i] << '\n';
}

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