Submission #267078

#	Time	Username	Problem	Language	Result	Execution time	Memory
267078		keko37	Examination (JOI19_examination)	C++14	100 / 100	491 ms	120404 KiB

examination

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 100005;
const int SIZ = 600005;

int n, q;
int x[MAXN], y[MAXN], z[MAXN], a[MAXN], b[MAXN], c[MAXN], ez[MAXN], sol[MAXN];
int fen[SIZ], pa[SIZ], pb[SIZ], pc[SIZ];
vector <int> saz, v[SIZ][3];
vector <pi> u[SIZ][3];

void ubaci (int x, int k) {
    for (; x < SIZ; x += x&-x) fen[x] += k;
}

int upit (int x) {
    int res = 0;
    for (; x > 0; x -= x&-x) res += fen[x];
    return res;
}

void sazmi () {
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    for (int i = 1; i <= n; i++) {
        x[i] = lower_bound(saz.begin(), saz.end(), x[i]) - saz.begin() + 1;
        y[i] = lower_bound(saz.begin(), saz.end(), y[i]) - saz.begin() + 1;
        z[i] = lower_bound(saz.begin(), saz.end(), z[i]) - saz.begin() + 1;
    }
    for (int i = 1; i <= q; i++) {
        a[i] = lower_bound(saz.begin(), saz.end(), a[i]) - saz.begin() + 1;
        b[i] = lower_bound(saz.begin(), saz.end(), b[i]) - saz.begin() + 1;
        c[i] = lower_bound(saz.begin(), saz.end(), c[i]) - saz.begin() + 1;
    }
}

void init () {
    for (int i = 1; i <= n; i++) {
        v[x[i]][0].push_back(y[i]);
        v[x[i]][1].push_back(z[i]);
        v[y[i]][2].push_back(z[i]);
        pa[x[i]]++; pb[y[i]]++; pc[z[i]]++;
    }
    for (int i = 1; i < SIZ; i++) {
        pa[i] += pa[i - 1];
        pb[i] += pb[i - 1];
        pc[i] += pc[i - 1];
    }
    for (int i = 1; i <= q; i++) {
        if (ez[i]) u[a[i]][0].push_back({b[i], i});
        if (!ez[i]) u[a[i]][1].push_back({c[i], i});
        if (!ez[i]) u[b[i]][2].push_back({c[i], i});
        sol[i] -= pa[a[i] - 1];
        sol[i] -= pb[b[i] - 1];
        if (!ez[i]) sol[i] -= pc[c[i] - 1];
    }
}

void sweep (int tip) {
    memset(fen, 0, sizeof fen);
    for (int i = 1; i < SIZ; i++) {
        for (auto e : u[i][tip]) {
            int val = e.first, ind = e.second;
            sol[ind] += upit(val - 1);
        }
        for (auto val : v[i][tip]) {
            ubaci(val, 1);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        z[i] = x[i] + y[i];
        saz.push_back(x[i]); saz.push_back(y[i]); saz.push_back(z[i]);
    }
    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i];
        ez[i] = c[i] <= a[i] + b[i];
        sol[i] = n;
        saz.push_back(a[i]); saz.push_back(b[i]); saz.push_back(c[i]);
    }
    sazmi();
    init();
    for (int i = 0; i < 3; i++) sweep(i);
    for (int i = 1; i <= q; i++) {
        cout << sol[i] << '\n';
    }
    return 0;
}

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