제출 #860080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860080		kh0i	Pairs (IOI07_pairs)	C++17	70 / 100	472 ms	477796 KiB

pairs

/**
 *	author: kh0i
 *	created: 17.06.2022 00:01:04
**/
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define gb(x) (x & (-x))
using ll = long long;

struct Dist{
    ll d1, d2, d3, d4;
};

struct Fenwick1D{
    vector<ll> bit;
    int n;
    Fenwick1D(int sz){
        bit.resize(sz + 2, 0);
        n = sz;
    }
    void add(int x, ll val){
        while(x <= n){
            bit[x] += val;
            x += gb(x);
        }
    }
    ll get(int x){
        ll res = 0;
        if(x > n) return 0;
        while(x > 0){
            res += bit[x];
            x -= gb(x);
        }
        return res;
    }
    ll query(int l, int r){
        return get(r) - get(l - 1);
    }
};

struct Fenwick2D{
    vector<Fenwick1D> bit;
    int n, m;
    Fenwick2D(int _n, int _m){
        n = _n, m = _m;
        bit.resize(n + 2, Fenwick1D(m + 2));
    }
    void add(int x, int y, ll val){
        while(x <= n){
            bit[x].add(y, val);
            x += gb(x);
        }
    }
    ll get(int x, int y){
        ll res = 0;
        if(x > n) return 0;
        while(x > 0){
            res += bit[x].get(y);
            x -= gb(x);
        }
        return res;
    }
    ll query(int x1, int y1, int x2, int y2){
        return get(x2, y2) - get(x2, y1 - 1) - get(x1 - 1, y2) + get(x1 - 1, y1 - 1);
    }
};

struct Fenwick3D{
    vector<Fenwick2D> bit;
    int n, m, k;
    Fenwick3D(int _n, int _m, int _k){
        n = _n, m = _m, k = _k;
        bit.resize(n, Fenwick2D(m, k));
    }
    void add(int x, int y, int z, ll val){
        while(x <= n){
            bit[x].add(y, z, val);
            x += gb(x);
        }
    }
    ll get(int x, int y, int z){
        ll res = 0;
        if(x > n) return 0;
        while(x > 0){
            res += bit[x].get(y, z);
            x -= gb(x);
        }
        return res;
    }
    ll query(int x1, int y1, int z1, int x2, int y2, int z2){
        return get(x2, y2, z2) - get(x1 - 1, y2, z2) - get(x2, y1 - 1, z2) - get(x2, y2, z1 - 1) +
               get(x1 - 1, y1 - 1, z2) + get(x1 - 1, y2, z1 - 1) + get(x2, y1 - 1, z1 - 1) -
               get(x1 - 1, y1 - 1, z1 - 1);
    }
};

const int N = 1e5 + 5;
ll n, b, d, m, x[N], y[N], z[N], ans;
Dist f[N];

void solve(){
    cin >> b >> n >> d >> m;
    if(b == 1){
        for(int i = 1; i <= n; ++i){
            cin >> x[i];
        }
        sort(x + 1, x + n + 1);
        ll l = 1;
        for(int i = 1; i <= n; ++i){
            while(x[i] - x[l] > d and l <= i) ++l;
            ans += i - l;
        }
        cout << ans;
    }
    else if(b == 2){
        for(int i = 1; i <= n; ++i){
            cin >> x[i] >> y[i];
            f[i].d1 = x[i] + y[i] - 1;
            f[i].d2 = x[i] - y[i] + m;
        }
        sort(f + 1, f + n + 1, [](Dist f, Dist s){ return f.d1 < s.d1; });
        Fenwick1D fen(75001 * 4);
        ll l = 1;
        for(int i = 1; i <= n; ++i){
            assert(f[i].d2 + d <= 75001 * 4 and f[i].d2 > 0);
            while(f[i].d1 - f[l].d1 > d){
                fen.add(f[l].d2, -1);
                ++l;
            }
            ans += fen.query(max(1ll, f[i].d2 - d), f[i].d2 + d);
//            debug(f[i].d1, f[i].d2, l, ans);
            fen.add(f[i].d2, 1);
        }
        cout << ans;
    }
    else{
        for(int i = 1; i <= n; ++i){
            cin >> x[i] >> y[i] >> z[i];
            f[i].d1 = x[i] + y[i] + z[i] - 2;
            f[i].d2 = x[i] + y[i] - z[i] + m;
            f[i].d3 = x[i] - y[i] + z[i] + m;
            f[i].d4 = x[i] - y[i] - z[i] + m + m;
        }
        if(d > 3 * m - 3){
            cout << 0;
            return;
        }
        Fenwick3D fen(76 * 4, 76 * 4, 76 * 4);
        sort(f + 1, f + n + 1, [](Dist f, Dist s){ return f.d1 < s.d1; });
        int l = 1;
        for(int i = 1; i <= n; ++i){
            assert(max({f[i].d2, f[i].d3, f[i].d4}) <= 76 * 4);
            while(f[i].d1 - f[l].d1 > d){
                fen.add(f[l].d2, f[l].d3, f[l].d4, -1);
                ++l;
            }
            ans += fen.query(max(1ll, f[i].d2 - d), max(1ll, f[i].d3 - d), max(1ll, f[i].d4 - d),
                                min(76ll * 4ll, f[i].d2 + d), min(76ll * 4ll, f[i].d3 + d), min(76ll * 4ll, f[i].d4 + d));
            debug(f[i].d1, f[i].d2, f[i].d3, f[i].d4, l, ans);
            fen.add(f[i].d2, f[i].d3, f[i].d4, 1);
        }
        cout << ans;
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    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: 0 / 10
• Subtask 11: 10 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10