Submission #1173265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173265		nguyenkhangninh99	Examination (JOI19_examination)	C++20	100 / 100	238 ms	47256 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define int long long

const int maxn = 1e5 + 7;
int ans[maxn];

struct event{
    int x, y, z;
} d[maxn];

struct query{
    int x, y, z, id;
} e[maxn];

vector<event> event1[maxn * 2], event2[maxn * 2];
vector<query> query1[maxn * 2], query2[maxn * 2];

vector<int> dx, dy, dz;
int get_x(int x) {
    return lower_bound(all(dx), x) - dx.begin() + 1;
}
int get_y(int x) {
    return lower_bound(all(dy), x) - dy.begin() + 1;
}
int get_z(int x) {
    return lower_bound(all(dz), x) - dz.begin() + 1;
}

struct FenwickTree{
    vector<int> bit;
    void init(int n){
        bit.assign(n + 5, 0);
    }
    void update(int u){
        for(u; u < bit.size(); u += (u & -u)) bit[u]++;
    }
    int get(int u) {
        int ans = 0;
        for(u; u > 0; u -= (u & -u)) ans += bit[u];
        return ans; 
    }
    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
} bitx, bity, bitz;

signed main() {
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(0);

    int n, q; cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> d[i].x >> d[i].y;
        d[i].z = d[i].x + d[i].y;
        dx.push_back(d[i].x);
        dy.push_back(d[i].y);
        dz.push_back(d[i].z);
    }

    for(int i = 1; i <= q; i++) {
        int x, y, z; cin >> x >> y >> z;
        dx.push_back(x); 
        dy.push_back(y); 
        dz.push_back(z);
        e[i] = {x, y, z, i};
    }

    sort(all(dx));
    sort(all(dy));
    sort(all(dz));
    dx.erase(unique(all(dx)), dx.end());
    dy.erase(unique(all(dy)), dy.end());
    dz.erase(unique(all(dz)), dz.end());

    for(int i = 1; i <= n; i++){
        d[i] = {get_x(d[i].x), get_y(d[i].y), get_z(d[i].z)};
        event1[d[i].z].push_back(d[i]);
        event2[d[i].x].push_back(d[i]);
    }

    for(int i = 1; i <= q; i++){
        bool ok = e[i].x + e[i].y < e[i].z;
        e[i] = {get_x(e[i].x), get_y(e[i].y), get_z(e[i].z), i};
        if(ok) query1[e[i].z].push_back(e[i]);
        else query2[e[i].x].push_back(e[i]);
    }

    int cur = 0;
    bitx.init(2 * n);
    bity.init(2 * n);
    bitz.init(2 * n);

    for(int i = 2 * n; i >= 1; i--){
        cur += event1[i].size();
        for(auto j: event1[i]) {
            bitx.update(j.x);
            bity.update(j.y);
        }
        for(auto j: query1[i]) ans[j.id] = bitx.get(j.x, n * 2) + bity.get(j.y, n * 2) - cur;
        for(auto j: event2[i]) bitz.update(j.y);
        for(auto j: query2[i]) ans[j.id] = bitz.get(j.y, n * 2);
    }

    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