oj.uz

Submission #715716

# Submission time Handle Problem Language Result Execution time Memory
715716 2023-03-27T15:29:29 Z gamigafy Pairs (IOI07_pairs) C++17
60 / 100
 385 ms 113100 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) + 2 * qry(x2-1, 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 1 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 26 ms 1084 KB Output is correct
2 Correct 26 ms 1080 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1548 KB Output is correct
2 Correct 42 ms 1444 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1440 KB Output is correct
2 Correct 43 ms 1448 KB Output is correct
3 Correct 47 ms 1572 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 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 54 ms 1572 KB Output is correct
2 Correct 42 ms 1568 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1832 KB Output is correct
2 Correct 57 ms 1868 KB Output is correct
3 Correct 52 ms 1740 KB Output is correct
4 Correct 57 ms 1828 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3276 KB Output is correct
2 Correct 75 ms 3364 KB Output is correct
3 Correct 72 ms 3244 KB Output is correct
4 Correct 70 ms 3248 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 110540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 2804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 59712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 385 ms 113100 KB Output isn't correct
2 Halted 0 ms 0 KB -