oj.uz

Submission #715799

# Submission time Handle Problem Language Result Execution time Memory
715799 2023-03-28T01:26:37 Z gamigafy Pairs (IOI07_pairs) C++17
100 / 100
 479 ms 112460 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(2*m+1);
    auto upd = [&](int i, int v) {
        for(i += m; i <= 2*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 1 ms 212 KB Output is correct
2 Correct 1 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 28 ms 932 KB Output is correct
2 Correct 29 ms 820 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 852 KB Output is correct
2 Correct 43 ms 940 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 936 KB Output is correct
2 Correct 44 ms 852 KB Output is correct
3 Correct 47 ms 852 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1332 KB Output is correct
2 Correct 42 ms 1236 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1292 KB Output is correct
2 Correct 58 ms 1336 KB Output is correct
3 Correct 55 ms 1236 KB Output is correct
4 Correct 55 ms 1344 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1816 KB Output is correct
2 Correct 74 ms 1840 KB Output is correct
3 Correct 67 ms 1836 KB Output is correct
4 Correct 77 ms 1832 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 110496 KB Output is correct
2 Correct 54 ms 110540 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2344 KB Output is correct
2 Correct 86 ms 2444 KB Output is correct
3 Correct 79 ms 2408 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 59180 KB Output is correct
2 Correct 302 ms 59100 KB Output is correct
3 Correct 183 ms 59088 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 112412 KB Output is correct
2 Correct 460 ms 112444 KB Output is correct
3 Correct 262 ms 112460 KB Output is correct