Submission #1271741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271741		dwuy	Examination (JOI19_examination)	C++20	0 / 100	153 ms	7612 KiB

examination

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

using namespace std;
using pii = pair<int, int>;

struct BIT{
    int n;
    vector<int> tree;

    BIT(int n = 0) : n(n), tree(n + 5, 0) {}

    void update(int idx, int val){
        for(; idx<=n; idx+=-idx&idx) tree[idx] += val;
    }

    int get(int idx){
        int res = 0;
        for(; idx; idx-=-idx&idx) res += tree[idx];
        return res;
    }

    void _update(int idx, int val){
        for(; idx; idx-=-idx&idx) tree[idx] += val;
    }

    int _get(int idx){
        int res = 0;
        for(; idx<=n; idx+=-idx&idx) res += tree[idx];
        return res;
    }
};

struct Query{
    int x, y, z, id;
};

const int MX = 200005;
int n, q;
int ans[MX];
Query a[MX];
Query qr[MX];
vector<int> rvx, rvy, rvz;

void pc1(){
    sort(qr + 1, qr + 1 + q, [](const Query &a, const Query &b){
        return a.x != b.x? a.x < b.x : a.y < b.y; 
    });
    sort(a + 1, a + 1 + n, [](const Query &a, const Query &b){
        return a.x != b.x? a.x < b.x : a.y < b.y;
    });
    BIT bit(rvy.size());
    for(int i=1, j=1; i<=q; i++){
        while(j <= n && a[j].x < qr[i].x){
            bit.update(a[j].y, 1);
            j++;
        }
        ans[qr[i].id] += bit.get(qr[i].y - 1);
    }
}

void pc2(){
    sort(qr + 1, qr + 1 + q, [](const Query &a, const Query &b){
        return a.z < b.z;
    });
    sort(a + 1, a + 1 + n, [](const Query &a, const Query &b){
        return a.z < b.z;
    });
    BIT X(rvx.size());
    BIT Y(rvy.size());
    for(int i=1, j=1; i<=q; i++){
        while(j <= n && a[j].z < qr[i].z){
            X.update(a[j].x, 1);
            Y.update(a[j].y, 1);
            j++;
        }
        ans[qr[i].id] += j - 1 - X.get(qr[i].x - 1) - Y.get(qr[i].y - 1);
    }
}

void pc3(){
    sort(qr + 1, qr + 1 + q, [](const Query &a, const Query &b){
        return a.x != b.x? a.x > b.x : a.y > b.y; 
    });
    sort(a + 1, a + 1 + n, [](const Query &a, const Query &b){
        return a.x != b.x? a.x > b.x : a.y > b.y;
    });
    BIT bit(rvy.size());
    for(int i=1, j=1; i<=q; i++){
        while(j <= n && a[j].x >= qr[i].x){
            bit._update(a[j].y, 1);
            j++;
        }
        ans[qr[i].id] = bit._get(qr[i].y) - ans[qr[i].id];
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for(int i=1; i<=n; i++){
        cin >> a[i].x >> a[i].y;
        a[i].z = a[i].x + a[i].y;
    }
    for(int i=1; i<=q; i++){
        int x, y, z;
        cin >> x >> y >> z;
        qr[i] = {x, y, z, i};
    }

    for(int i=1; i<=n; i++){
        rvx.push_back(a[i].x);
        rvy.push_back(a[i].y);
        rvz.push_back(a[i].z);
    }
    for(int i=1; i<=q; i++){
        rvx.push_back(qr[i].x);
        rvy.push_back(qr[i].y);
        rvz.push_back(qr[i].z);
    }
    sort(all(rvx)); 
    sort(all(rvy)); 
    sort(all(rvz));
    rvx.erase(unique(all(rvx)), rvx.end());
    rvy.erase(unique(all(rvy)), rvy.end());
    rvz.erase(unique(all(rvz)), rvz.end());
    for(int i=1; i<=n; i++){
        a[i].x = lower_bound(all(rvx), a[i].x) - rvx.begin() + 1;
        a[i].y = lower_bound(all(rvy), a[i].y) - rvy.begin() + 1;
        a[i].z = lower_bound(all(rvz), a[i].z) - rvz.begin() + 1;
    }
    for(int i=1; i<=q; i++){
        qr[i].x = lower_bound(all(rvx), qr[i].x) - rvx.begin() + 1;
        qr[i].y = lower_bound(all(rvy), qr[i].y) - rvy.begin() + 1;
        qr[i].z = lower_bound(all(rvz), qr[i].z) - rvz.begin() + 1;
    }

    pc1();
    pc2();
    pc3();

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

    return 0;
}

/*

5 1
 35 100
 70 70
 45 15
 80 40
 20 95
 60 60 80
 10 10 100
 20 50 120
 0 100 100

*/

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