Submission #860080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
860080	2023-10-11T14:54:45 Z	kh0i	Pairs (IOI07_pairs)	C++17	70 / 100	472 ms	477796 KB

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.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct

Subtask #2
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1628 KB	Output is correct
2	Correct	10 ms	1628 KB	Output is correct

Subtask #4
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	2004 KB	Output is correct
2	Correct	16 ms	2012 KB	Output is correct

Subtask #5
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	2092 KB	Output is correct
2	Correct	14 ms	1888 KB	Output is correct
3	Correct	14 ms	1884 KB	Output is correct

Subtask #6
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4700 KB	Output is correct
2	Correct	1 ms	4700 KB	Output is correct

Subtask #7
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	8796 KB	Output is correct
2	Correct	18 ms	8796 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	8784 KB	Output is correct
2	Correct	23 ms	9048 KB	Output is correct
3	Correct	22 ms	9008 KB	Output is correct
4	Correct	22 ms	8788 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	9308 KB	Output is correct
2	Correct	28 ms	9412 KB	Output is correct
3	Correct	26 ms	9360 KB	Output is correct
4	Correct	26 ms	9308 KB	Output is correct

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	231760 KB	Output is correct
2	Runtime error	264 ms	469832 KB	Execution killed with signal 11
3	Halted	0 ms	0 KB	-

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	236012 KB	Output is correct
2	Correct	177 ms	235948 KB	Output is correct
3	Correct	149 ms	235856 KB	Output is correct

Subtask #12
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	307 ms	236372 KB	Output is correct
2	Correct	383 ms	236164 KB	Output is correct
3	Runtime error	342 ms	477676 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #13
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	433 ms	236112 KB	Output is correct
2	Correct	472 ms	236112 KB	Output is correct
3	Runtime error	314 ms	477796 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Submission #860080

Compilation message