Submission #1248312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248312		nh0902	Examination (JOI19_examination)	C++20	100 / 100	550 ms	13196 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

const int M = 1e5 + 10;

const int inf = 1e18;

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

void compress(int *p, int m) {
    vector<pair<int, int>> v;
    for (int i = 1; i <= m; i ++) {
        v.push_back({p[i], i});
    }
    sort(v.begin(), v.end());
    p[v[0].second] = 1;
    for (int i = 1; i < m; i ++) {
        p[v[i].second] = p[v[i - 1].second];
        if (v[i].first > v[i - 1].first) p[v[i].second] ++;
    }
}

void prep() {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) {
        cin >> x[i] >> y[i];
        z[i] = x[i] + y[i];
    }
    for (int i = 1; i <= q; i ++) {
        cin >> x[i + n] >> y[i + n] >> z[i + n];
    }
    compress(x, n + q);
    compress(y, n + q);
    compress(z, n + q);
    //for (int i = 1; i <= n + q; i ++) cout << z[i] << " ";
    //cout << "\n";
}

int bit[N];

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

void update(int u, int v) {
    int idx = u;
    while (idx <= n + q) {
        bit[idx] += v;
        idx += (idx & (-idx));
    }
}

int order[2 * N];

bool cmp(int a, int b) {
    if (x[a] == x[b]) return a > b;
    return x[a] < x[b];
}

bool cmp2(int a, int b) {
    int i = order[a];
    int j = order[b];
    if (y[i] == y[j]) {
        if (z[i] == z[j]) {
            return i < j;
        }
        return z[i] > z[j];
    }
    return y[i] > y[j];
}

void dvc(int l, int r) {
    if (l >= r) return;

    //cout << l << " ; " << r << "\n";

    int mid = (l + r) / 2;

    vector<int> v;
    for (int i = l; i <= r; i ++) v.push_back(i);
    sort(v.begin(), v.end(), cmp2);

    for (int i : v) {
        //cout << i << " " << y[order[i]] << " " << z[order[i]] << "\n";

        if (i > mid && order[i] <= n) update(z[order[i]], 1);
            //cout << order[i] << "\n";

        if (i <= mid && order[i] > n) {
            ans[order[i] - n] += getSum(n + q) - getSum(z[order[i]] - 1);
            //cout << order[i] << " " << n + q << " " << z[order[i]] - 1 << " " << getSum(n + q) << " " << getSum(z[order[i]] - 1) << "\n";
        }
    }

    //cout << "\n";

    for (int i : v) {
        if (i > mid && order[i] <= n) update(z[order[i]], - 1);
    }

    dvc(l, mid);
    dvc(mid + 1, r);


}

void solve() {
    for (int i = 1; i <= n + q; i ++) order[i] = i;
    sort(order + 1, order + n + q + 1, cmp);
    //for (int i = 1; i <= n + q; i ++) cout << order[i] << " " << x[order[i]] << " " << y[order[i]] << " " << z[order[i]] << "\n";
    dvc(1, n + q);
    for (int i = 1; i <= q; i ++) cout << ans[i] << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();

    return 0;
}

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