Submission #1138612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138612		quannnguyen2009	Pairs (IOI07_pairs)	C++20	100 / 100	947 ms	138960 KiB

pairs

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

int b, n, d, m;

// 1d array
namespace oned {

const int N = 1e5+5;
int a[N];

void solve() {
    for (int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    int ans = 0;
    for (int i=1; i<=n; i++) ans += (upper_bound(a+1, a+n+1, a[i]+d)-a)-i-1;
    cout << ans;
}


}


// 2d array
namespace twod {


const int N = 3e5+5, offset = 1e5, L = 1e4, R = 3e5;
ii a[N/3];
vector<int> BIT[N];
vector<int> idx[N];

void prep_upd(int x, int y) {
    for (int i=x; i<N; i+=(i&-i)) idx[i].pb(y);
}

void prep_get(int x, int y) {
    for (int i=x; i; i-=(i&-i)) idx[i].pb(y);
}

void upd(int x, int y, int v) {
    for (int i=x; i<N; i+=(i&-i)) {
        for (int j=lower_bound(all(idx[i]), y)-idx[i].begin(); j<sz(BIT[i]); j+=(j&-j)) BIT[i][j] += v;
    }
}

int get(int x, int y) {
    int ans = 0;
    for (int i=x; i; i-=(i&-i)) {
        for (int j=lower_bound(all(idx[i]), y)-idx[i].begin(); j; j-=(j&-j)) ans += BIT[i][j];
    }
    return ans;
}

void solve() {
    for (int i=1; i<=n; i++) {
        cin >> a[i].fi >> a[i].se;
        int x = a[i].fi+a[i].se+offset, y = a[i].fi-a[i].se+offset;
        a[i] = {x, y};
        prep_upd(x, y);
    }
    for (int i=1; i<=n; i++) {
        int x1 = max(a[i].fi-d, 10000LL), y1 = max(a[i].se-d, 10000LL), x2 = min(a[i].fi+d, 300000LL), y2 = min(a[i].se+d, 300000LL);
        prep_get(x2, y2); prep_get(x1-1, y2); prep_get(x2, y1-1); prep_get(x1-1, y1-1);
    }
    for (int i=1; i<N; i++) {
        idx[i].pb(0);
        sort(all(idx[i]));
        idx[i].erase(unique(all(idx[i])), idx[i].end());
        BIT[i].resize(sz(idx[i]), 0);
    }
    for (int i=1; i<=n; i++) upd(a[i].fi, a[i].se, 1);
    int ans = 0;
    for (int i=1; i<=n; i++) {
        int x1 = max(a[i].fi-d, 10000LL), y1 = max(a[i].se-d, 10000LL), x2 = min(a[i].fi+d, 300000LL), y2 = min(a[i].se+d, 300000LL);
        ans += get(x2, y2)-get(x1-1, y2)-get(x2, y1-1)+get(x1-1, y1-1);
    }
    cout << (ans-n)/2;
}


}


//3d array
namespace threed {


const int N = 1e5+5, M = 250, offset = 76;
struct Obj {
    int x, y, z; 
} a[N];
int dp[M][M][M];

int cal(int i, int x1, int y1, int x2, int y2) {
    return dp[i][x2][y2]-dp[i][x1-1][y2]-dp[i][x2][y1-1]+dp[i][x1-1][y1-1];
}

void solve() {
    for (int i=1; i<=n; i++) {
        int x, y, z; cin >> x >> y >> z;
        a[i] = {x, y+z+offset, y-z+offset};   
        dp[a[i].x][a[i].y][a[i].z]++;
    }
    for (int i=1; i<M; i++) {
        for (int j=1; j<M; j++) {
            for (int k=1; k<M; k++) dp[i][j][k] += dp[i][j][k-1]+dp[i][j-1][k]-dp[i][j-1][k-1];
        }
    }
    int ans = 0;
    for (int i=1; i<=n; i++) {
        auto [x, y, z] = a[i];
        for (int j=d; j>=0; j--) {
            int I = x-(d-j);
            if(I<0) break;
            int x1 = max(y-j, 1LL), y1 = max(z-j, 1LL), x2 = min(y+j, M-1), y2 = min(z+j, M-1);
            ans += cal(I, x1, y1, x2, y2);
        }
        for (int j=d-1; j>=0; j--) {
            int I = x+(d-j);
            if(I>=M) break;
            int x1 = max(y-j, 1LL), y1 = max(z-j, 1LL), x2 = min(y+j, M-1), y2 = min(z+j, M-1);
            ans += cal(I, x1, y1, x2, y2);
        }
    }
    cout << (ans-n)/2;
}


}



signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> b >> n >> d >> m;
    if(b==1) {
        using namespace oned;
        solve();
    } else if(b==2) {
        using namespace twod;
        solve();
    } else {
        using namespace threed;
        solve();
    }
}

• 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