제출 #1086962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086962		DylanSmith	Pairs (IOI07_pairs)	C++17	100 / 100	202 ms	53764 KiB

pairs

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#define lb(x,y) lower_bound(all(x),y)-begin(x)

mt19937 rng;

int query(vector<int> &tree, int i) {
    int res = 0;
    for (int x = i; x; x -= x & -x) res += tree[x];
    return res;
}

int query(vector<vector<vector<int>>> &tree, int a, int b, int c) {
    ll res = 0;
    for (int x = a; x; x -= x & -x)
        for (int y = b; y; y -= y & -y)
            for (int z = c; z; z -= z & -z)
                res += tree[x][y][z];
    return res;
}

void solve() {
    int B, N, D, M; cin >> B >> N >> D >> M;
    if (B == 1) {
        vector<int> a(N);
        for (int i = 0; i < N; i++) cin >> a[i];
        sort(all(a));
        int j = 0;
        ll res = 0;
        for (int i = 0; i < N; i++) {
            while (a[i] - a[j] > D) j++;
            res += i - j;
        }
        cout << res << "\n";
    } else if (B == 2) {
        vector<int> tree(150001, 0);
        vector<pair<int, int>> points;
        for (int i = 0; i < N; i++) {
            int x, y; cin >> x >> y;
            int p1 = x + y, p2 = x - y + 75000;
            points.pb({p1, p2});
        }
        sort(all(points));
        int j = 0;
        ll res = 0;
        for (int i = 0; i < N; i++) {
            while (points[i].first - points[j].first > D) {
                for (int x = points[j].second; x <= 150000; x += x & -x)
                    tree[x]--;
                j++;
            }
            res += query(tree, min(150000, points[i].second + D));
            if (points[i].second - D - 1 > 0) res -= query(tree, points[i].second - D - 1);
            for (int x = points[i].second; x <= 150000; x += x & -x)
                tree[x]++;
        }
        cout << res << "\n";
    } else {
        vector<vector<int>> points;
        for (int i = 0; i < N; i++) {
            int x, y, z; cin >> x >> y >> z;
            int p1 = x + y + z, p2 = -x + y + z + 75, p3 = x - y + z + 75, p4 = x + y - z + 75;
            points.pb({p1, p2, p3, p4});
        }
        sort(all(points));
        vector<vector<vector<int>>> tree(226, vector<vector<int>>(226, vector<int>(226, 0)));
        int j = 0;
        ll res = 0;
        for (int i = 0; i < N; i++) {
            while (points[i][0] - points[j][0] > D) {
                for (int x = points[j][1]; x <= 225; x += x & -x)
                    for (int y = points[j][2]; y <= 225; y += y & -y)
                        for (int z = points[j][3]; z <= 225; z += z & -z)
                            tree[x][y][z]--;
                j++;
            }
            int a = points[i][1], b = points[i][2], c = points[i][3];
            int a2 = min(225, a + D), b2 = min(225, b + D), c2 = min(225, c + D);
            res += query(tree, a2, b2, c2);
            if (a - D - 1 > 0) res -= query(tree, a - D - 1, b2, c2);
            if (b - D - 1 > 0) res -= query(tree, a2, b - D - 1, c2);
            if (c - D - 1 > 0) res -= query(tree, a2, b2, c - D - 1);
            if (a - D - 1 > 0 && b - D - 1 > 0) res += query(tree, a - D - 1, b - D - 1, c2);
            if (a - D - 1 > 0 && c - D - 1 > 0) res += query(tree, a - D - 1, b2, c - D - 1);
            if (b - D - 1 > 0 && c - D - 1 > 0) res += query(tree, a2, b - D - 1, c - D - 1);
            if (a - D - 1 > 0 && b - D - 1 > 0 && c - D - 1 > 0) res -= query(tree, a - D - 1, b - D - 1, c - D - 1);
            for (int x = points[i][1]; x <= 225; x += x & -x)
                for (int y = points[i][2]; y <= 225; y += y & -y)
                    for (int z = points[i][3]; z <= 225; z += z & -z)
                        tree[x][y][z]++;
        }
        cout << res << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());

    solve();

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10