oj.uz

Submission #715725

# Submission time Handle Problem Language Result Execution time Memory
715725 2023-03-27T16:26:32 Z gamigafy Pairs (IOI07_pairs) C++17
100 / 100
 481 ms 113080 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sz(x) (int)(x.size())

int b, n, m, d;

void solve1D() {
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());

    ll ans = 0;
    for (int l = 0, r = 0; l < n; l++) {
        while (r < n && a[r] - a[l] <= d)
            r++;
        ans += r - l - 1;
    }
    cout << ans << '\n';
}

void solve2D() {
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x + y, x - y};
    }
    sort(a.begin(), a.end());

    vector<int> c(4*m+1);
    auto upd = [&](int i, int v) {
        for(i += m; i <= 4*m; i += i&-i) c[i] += v;
    };
    auto qry = [&](int i)  {
        int res = 0;
        for (i += m; i > 0; i -= i&-i) res += c[i];
        return res;
    };

    ll ans = 0;
    for (int l = 0, r = 0; l < n; l++) {
        while (r < n && a[r].first - a[l].first <= d)
            upd(a[r++].second, 1);
        upd(a[l].second, -1);
        ans += qry(min(a[l].second + d, m)) - qry(max(a[l].second - d - 1, -m));
    }
    cout << ans << '\n';
}

void solve3D() {
    vector<array<int, 4>> a(n);
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[i] = {x + y + z, x + y - z, x - y + z, x - y - z};
    }
    sort(a.begin(), a.end());

    vector c(4*m+1, vector(4*m+1, vector<int>(4*m+1)));
    auto upd = [&](int x, int y, int z, int v) {
        for (int i = x + 2*m; i <= 4*m; i += i&-i)
            for (int j = y + 2*m; j <= 4*m; j += j&-j)
                for (int k = z + 2*m; k <= 4*m; k += k&-k)
                    c[i][j][k] += v;
    };
    auto qry = [&](int x, int y, int z) {
        int res = 0;
        for (int i = x + 2*m; i > 0; i -= i&-i)
            for (int j = y + 2*m; j > 0; j -=j&-j)
                for (int k = z + 2*m; k > 0; k -= k&-k)
                    res += c[i][j][k];
        return res;
    };
    auto sum = [&](int x1, int y1, int z1, int x2, int y2, int z2) {
        return qry(x1, y1, z1) - qry(x2, y1, z1) - qry(x1, y2, z1) - qry(x1, y1, z2)
                + qry(x1, y2, z2) + qry(x2, y1, z2) + qry(x2, y2, z1) - qry(x2, y2, z2);
    };

    ll ans = 0;
    for (int l = 0, r = 0; l < n; l++) {
        while (r < n && a[r][0] - a[l][0] <= d) {
            upd(a[r][1], a[r][2], a[r][3], 1);
            r++;
        }
        upd(a[l][1], a[l][2], a[l][3], -1);
        ans += sum(min(a[l][1] + d, 2 * m), min(a[l][2] + d, 2 * m), min(a[l][3] + d, 2 * m), 
            max(a[l][1] - d - 1, -2 * m), max(a[l][2] - d - 1, -2 * m), max(a[l][3] - d - 1, -2 * m));
    }
    cout << ans << '\n';
}

int main() {
    cin >> b >> n >> d >> m;

    if (b == 1) {
        solve1D();
    } else if (b == 2) {
        solve2D();
    } else {
        solve3D();
    }
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 720 KB Output is correct
2 Correct 27 ms 816 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 876 KB Output is correct
2 Correct 45 ms 724 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 804 KB Output is correct
2 Correct 52 ms 776 KB Output is correct
3 Correct 54 ms 816 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1180 KB Output is correct
2 Correct 42 ms 1108 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 1208 KB Output is correct
2 Correct 54 ms 1116 KB Output is correct
3 Correct 53 ms 1104 KB Output is correct
4 Correct 56 ms 1168 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2248 KB Output is correct
2 Correct 70 ms 2224 KB Output is correct
3 Correct 66 ms 2200 KB Output is correct
4 Correct 66 ms 2176 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 110608 KB Output is correct
2 Correct 53 ms 110504 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 2252 KB Output is correct
2 Correct 84 ms 2808 KB Output is correct
3 Correct 72 ms 2748 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 59084 KB Output is correct
2 Correct 349 ms 59816 KB Output is correct
3 Correct 162 ms 59776 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 440 ms 112368 KB Output is correct
2 Correct 481 ms 112996 KB Output is correct
3 Correct 270 ms 113080 KB Output is correct