oj.uz

Submission #1086962

# Submission time Handle Problem Language Result Execution time Memory
1086962 2024-09-11T22:17:27 Z DylanSmith Pairs (IOI07_pairs) C++17
100 / 100
 202 ms 53764 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1164 KB Output is correct
2 Correct 9 ms 1116 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1488 KB Output is correct
2 Correct 13 ms 1628 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1624 KB Output is correct
2 Correct 13 ms 1628 KB Output is correct
3 Correct 12 ms 1628 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2780 KB Output is correct
2 Correct 18 ms 2640 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2776 KB Output is correct
2 Correct 23 ms 2824 KB Output is correct
3 Correct 25 ms 2780 KB Output is correct
4 Correct 21 ms 2776 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3036 KB Output is correct
2 Correct 25 ms 3036 KB Output is correct
3 Correct 24 ms 3036 KB Output is correct
4 Correct 24 ms 2916 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47448 KB Output is correct
2 Correct 20 ms 47452 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 53460 KB Output is correct
2 Correct 102 ms 53504 KB Output is correct
3 Correct 126 ms 53500 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 53764 KB Output is correct
2 Correct 185 ms 53764 KB Output is correct
3 Correct 76 ms 53752 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 53760 KB Output is correct
2 Correct 189 ms 53756 KB Output is correct
3 Correct 82 ms 53764 KB Output is correct