Submission #715799

#	Time	Username	Problem	Language	Result	Execution time	Memory
715799		gamigafy	Pairs (IOI07_pairs)	C++17	100 / 100	479 ms	112460 KiB

pairs

#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 / 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