Submission #1185479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185479		Gray	Pairs (IOI07_pairs)	C++20	67 / 100	481 ms	589824 KiB

pairs

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)


struct Fenwick{
    vector<vector<vector<ll>>> tr; ll n, offs;
    Fenwick(ll N){
        n=N+20; offs=10;
        tr.resize(n+1, vector(n+1, vector<ll>(n+1)));
    }
    void add(ll _i, ll _j, ll _k, ll x){
        _i+=offs; _j+=offs; _k+=offs;
        for (; _i<=n; _i+=(-_i&_i)){
            for (ll j=_j; j<=n; j+=(-j&j)){
                for (ll k=_k; k<=n; k+=(-k&k)){
                    tr[_i][j][k]+=x;
                }
            }
        }
    }
    ll query(ll _i, ll _j, ll _k){
        _i+=offs; _j+=offs; _k+=offs; ll sum=0;
        for (ll i=_i; i; i-=(-i&i)){
            for (ll j=_j; j; j-=(-j&j)){
                for (ll k=_k; k; k-=(-k&k)){
                    sum+=tr[i][j][k];
                }
            }
        }
        return sum;
    }
};

void solve(){
    ll b, n, d, m; cin >> b >> n >> d >> m; m++;
    if (b==1){
        vector<int> cord(m+1), pref(m+1);
        for (ll i=1; i<=n; i++){
            ll x; cin >> x;
            x++; cord[x]++;
        }
        for (ll i=1; i<=m; i++){
            pref[i]+=pref[i-1]+cord[i];
        }
        ll res=0;
        for (ll i=1; i<=m; i++){
            if (cord[i]) res+=(ll)cord[i]*(ll)(+pref[min(m, i+d)]-pref[max(0ll, i-d-1)]-1);
        }
        cout << res/2 << ln;
    }else if (b==2){
        vector<vector<int>> to(2*m+1, vector<int>(2*m+1));
        for (ll i=0; i<n; i++){
            ll x, y; cin >> x >> y; x++; y++;
            to[x+y][x-y+m]++;
        }
        m=2*m;
        vector<vector<int>> pref(m+1, vector<int>(m+1));
        for (ll i=1; i<=m; i++){
            for (ll j=1; j<=m; j++){
                pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+to[i][j];
            }
        }
        ll res=0;
        for (ll i=0; i<=m; i++){
            for (ll j=0; j<=m; j++){
                if (to[i][j]) {
                    ll fi=max(0ll, i-d-1), fj = max(0ll, j-d-1);
                    ll ti = min(m, i+d), tj = min(m, j+d);
                    res+=(ll)(pref[ti][tj]-pref[ti][fj]-pref[fi][tj]+pref[fi][fj]-1)*(ll)to[i][j];
                }
            }
        }
        cout << res/2 << ln;
    }else{
        ll res=0;
        vector<array<ll, 4>> a(n);
        for (ll i=0; i<n; i++){
            ll x, y, z; cin >> x >> y >> z; x++; y++; z++;
            a[i] = {x+y+z, x-y+z+m, x+y-z+m, x-y-z+2*m};
        }
        m=3*m;
        sort(a.begin(), a.end());
        ll l=0, r=-1; Fenwick tr(m);
        for (ll i=0; i<n; i++){
            while (l+1<=i and a[i][0]-a[l][0]>d) {
                tr.add(a[l][1], a[l][2], a[l][3], -1); l++;
            }
            while (r+1<n and a[r+1][0]-a[i][0]<=d){
                r++; tr.add(a[r][1], a[r][2], a[r][3], 1);
            }
            ll fx = max(a[i][1]-d-1, 0ll), fy = max(a[i][2]-d-1, 0ll), fz=max(a[i][3]-d-1, 0ll);
            ll tx = min(a[i][1]+d, m), ty = min(a[i][2]+d, m), tz=min(a[i][3]+d, m);
            // cout << tr.query(tx, ty, tz)-tr.query(tx, fy, tz)-tr.query(fx, ty, tz)-tr.query(tx, ty, fz)+tr.query(fx, fy, tz)+tr.query(fx, ty, fz)+tr.query(tx, fy, fz)-tr.query(fx, fy, fz)-1 << ln;
            res += tr.query(tx, ty, tz)-tr.query(tx, fy, tz)-tr.query(fx, ty, tz)-tr.query(tx, ty, fz)+tr.query(fx, fy, tz)+tr.query(fx, ty, fz)+tr.query(tx, fy, fz)-tr.query(fx, fy, fz)-1;
        }
        cout << res/2 << ln;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 6
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10