Submission #1185502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185502		Gray	Pairs (IOI07_pairs)	C++20	100 / 100	206 ms	126860 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;
    }
};

struct Fenwicke{
    vector<ll> tr;
    ll n, offs;
    Fenwicke(ll N){
        n=N+20; offs=10; tr.resize(n+1);
    }
    void add(ll i, ll x){
        i+=offs; for (; i<=n; i+=(-i&i)) tr[i]+=x;
    }
    ll get(ll i){
        i+=offs; ll sum=0;
        for (; i; i-=(-i&i)) sum+=tr[i];
        return sum;
    }
};

void solve(){
    ll b, n, d, m; cin >> b >> n >> d >> m; m++;
    if (b==1){
        vector<ll> xs;
        for (ll i=1; i<=n; i++){
            ll x; cin >> x;
            xs.push_back(x);
        }
        sort(xs.begin(), xs.end());
        ll l=0, r=-1, res=0;
        for (ll i=0; i<n; i++){
            while (l+1<=i and xs[i]-xs[l]>d) {
                l++;
            }
            while (r+1<n and xs[r+1]-xs[i]<=d){
                r++;
            }
            res+=max(0ll, r-l);
        }
        cout << res/2 << ln;
    }else if (b==2){
        vector<array<ll, 2>> a(n);
        for (ll i=0; i<n; i++){
            ll x, y; cin >> x >> y; x++; y++;
            a[i] = {x+y, x-y+m};
        }
        Fenwicke tr(2*m);
        sort(a.begin(), a.end());
        // for (auto [x, y]:a) cout << x << " - " << y << ln;
        ll l=0, r=-1, res=0;
        for (ll i=0; i<n; i++){
            while (l+1<=i and a[i][0]-a[l][0]>d) {
                tr.add(a[l][1], -1); l++;
                // cout << "H" << ln;
            }
            while (r+1<n and a[r+1][0]-a[i][0]<=d){
                r++; tr.add(a[r][1], 1);
                // cout << "AH" << ln;
            }
            // cout << l << " : " << i << " : " << r << "&" << d << " -> ";
            ll fx = max(a[i][1]-d-1, 0ll);
            ll tx = min(a[i][1]+d, 2*m);
            // cout << tr.get(tx)-tr.get(fx)-1 << ln;
            res += tr.get(tx)-tr.get(fx)-1;
        }
        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: 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