oj.uz

Submission #636112

# Submission time Handle Problem Language Result Execution time Memory
636112 2022-08-28T07:04:15 Z Spade1 Pairs (IOI07_pairs) C++14
100 / 100
 198 ms 28312 KB 
#include<bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int N = 2e5 + 10;
const int M = 250;

int a[N], fw[N], fw2[M][M][M];
pii c[N], e[N];
pair<int, pii> f[N];
pair<pii, pii> g[N];

void update1(int i, int val) {
    for (; i < N; i += i&-i) {
        fw[i] += val;
    }
}

int query1(int i) {
    int ret = 0;
    for (; i > 0; i -= i&-i) {
        ret += fw[i];
    }
    return ret;
}

void update2(int ii, int jj, int kk, int val) {
    for (int i = ii; i < M; i += i&-i) {
        for (int j = jj; j < M; j += j&-j) {
            for (int k = kk; k < M; k += k&-k) {
                fw2[i][j][k] += val;
            }
        }
    }
}

int query2(int ii, int jj, int kk) {
    int ret = 0;
    for (int i = ii; i > 0; i -= i&-i) {
        for (int j = jj; j > 0; j -= j&-j) {
            for (int k = kk; k > 0; k -=k&-k) {
                ret += fw2[i][j][k];
            }
        }
    }
    return ret;
}

void solve() {
    int b, n, d, m; cin >> b >> n >> d >> m;
    ll ans = 0;
    if (b == 1) {
        for (int i = 0; i < n; ++i) cin >> a[i];
        sort(a, a+n);
        int l = 0;
        for (int i = 1; i < n; ++i) {
            while (a[i] - a[l] > d) l++;
            ans += (i-l);
        }
    }
    else if (b == 2) {
        for (int i = 0; i < n; ++i) cin >> c[i].st >> c[i].nd;
        for (int i = 0; i < n; ++i) {
            e[i].st = c[i].st - c[i].nd;
            e[i].nd = c[i].st + c[i].nd + 1;
        }
        sort(e, e+n);
        int l = 0;
        update1(e[0].nd, 1);
        for (int i = 1; i < n; ++i) {
            while (e[i].st - e[l].st > d) {
                update1(e[l].nd, -1);
                l++;
            }
            ans += (query1(e[i].nd + d) - query1(max(1, e[i].nd - d - 1)));
            update1(e[i].nd, 1);
        }
    }
    else if (b == 3) {
        for (int i = 0; i < n; ++i) {
            cin >> f[i].st >> f[i].nd.st >> f[i].nd.nd;
        }
        for (int i = 0; i < n; ++i) {
            g[i].st.st = f[i].st - f[i].nd.st - f[i].nd.nd;
            g[i].st.nd = f[i].st + f[i].nd.st + f[i].nd.nd+1;
            g[i].nd.st = f[i].st + f[i].nd.st - f[i].nd.nd+76;
            g[i].nd.nd = f[i].st - f[i].nd.st + f[i].nd.nd+76;
        }
        sort(g, g+n);
        int l = 0;
        update2(g[0].st.nd, g[0].nd.st, g[0].nd.nd, 1);
        for (int i = 1; i < n; ++i) {
            while (g[i].st.st - g[l].st.st > d) {
                update2(g[l].st.nd, g[l].nd.st, g[l].nd.nd, -1);
                l++;
            }
            ans += query2(min(249, g[i].st.nd + d), min(249, g[i].nd.st + d), min(249, g[i].nd.nd + d));
            ans -= query2(min(249, g[i].st.nd + d), min(249, g[i].nd.st + d), max(1, g[i].nd.nd - d - 1));
            ans -= query2(min(249, g[i].st.nd + d), max(1, g[i].nd.st - d - 1), min(249, g[i].nd.nd + d));
            ans -= query2(max(1, g[i].st.nd - d - 1), min(249, g[i].nd.st + d), min(249, g[i].nd.nd + d));
            ans += query2(min(249, g[i].st.nd + d), max(1, g[i].nd.st - d - 1), max(1, g[i].nd.nd - d - 1));
            ans += query2(max(1, g[i].st.nd - d - 1), min(249, g[i].nd.st + d), max(1, g[i].nd.nd - d - 1));
            ans += query2(max(1, g[i].st.nd - d - 1), max(1, g[i].nd.st - d - 1), min(249, g[i].nd.nd + d));
            ans -= query2(max(1, g[i].st.nd - d - 1), max(1, g[i].nd.st - d - 1), max(1, g[i].nd.nd - d - 1));
            update2(g[i].st.nd, g[i].nd.st, g[i].nd.nd, 1);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 716 KB Output is correct
2 Correct 16 ms 660 KB Output is correct
3 Correct 17 ms 716 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1852 KB Output is correct
2 Correct 24 ms 1944 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1876 KB Output is correct
2 Correct 30 ms 1892 KB Output is correct
3 Correct 28 ms 1932 KB Output is correct
4 Correct 27 ms 1920 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2452 KB Output is correct
2 Correct 28 ms 2388 KB Output is correct
3 Correct 28 ms 2380 KB Output is correct
4 Correct 30 ms 2336 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3856 KB Output is correct
2 Correct 79 ms 3836 KB Output is correct
3 Correct 66 ms 3804 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 19408 KB Output is correct
2 Correct 181 ms 19504 KB Output is correct
3 Correct 88 ms 19440 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 27508 KB Output is correct
2 Correct 169 ms 27468 KB Output is correct
3 Correct 96 ms 28312 KB Output is correct