oj.uz

답안 #686130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
686130 2023-01-25T05:57:58 Z finn__ Pairs (IOI07_pairs) C++17
100 / 100
 377 ms 45672 KB 
#include <bits/stdc++.h>
using namespace std;

template <typename T>
class FenwickTree3d
{
    vector<T> t;
    array<int64_t, 3> n;

public:
    FenwickTree3d(array<int64_t, 3> const &_n)
    {
        n = _n;
        t = vector<T>(n[0] * n[1] * n[2], 0);
    }

private:
    int64_t get_index(array<int64_t, 3> const &i) const
    {
        return (i[0] - 1) * n[1] * n[2] + (i[1] - 1) * n[2] + i[2] - 1;
    }

    T prefix_sum(array<int64_t, 3> i) const
    {
        T x = 0;
        i[0]++, i[1]++, i[2]++;

        while (i[0])
        {
            int64_t u = i[1];
            while (u)
            {
                int64_t v = i[2];
                while (v)
                {
                    x += t[get_index({i[0], u, v})];
                    v -= v & -v;
                }
                u -= u & -u;
            }
            i[0] -= i[0] & -i[0];
        }

        return x;
    }

public:
    T range_sum(array<int64_t, 3> i, array<int64_t, 3> j) const
    {
        for (unsigned k = 0; k < 3; k++)
        {
            i[k] = min<T>(max<T>(i[k], 0), n[k] - 1);
            j[k] = min<T>(max<T>(j[k], 0), n[k] - 1);
        }

        T x = 0;
        for (unsigned k = 0; k < 8; k++)
        {
            array<int64_t, 3> const a = {k & 1 ? i[0] - 1 : j[0],
                                         k & 2 ? i[1] - 1 : j[1],
                                         k & 4 ? i[2] - 1 : j[2]};
            if (a[0] >= 0 && a[1] >= 0 && a[2] >= 0)
                x += prefix_sum(a) * ((__builtin_popcount(k) & 1) ? -1 : 1);
        }
        return x;
    }

    void increment(array<int64_t, 3> i, T x)
    {
        i[0]++, i[1]++, i[2]++;

        while (i[0] <= n[0])
        {
            int64_t u = i[1];
            while (u <= n[1])
            {
                int64_t v = i[2];
                while (v <= n[2])
                {
                    t[get_index({i[0], u, v})] += x;
                    v += v & -v;
                }
                u += u & -u;
            }
            i[0] += i[0] & -i[0];
        }
    }
};

typedef array<int64_t, 4> Quaternion;

Quaternion quaternion_multiply(Quaternion const &p, Quaternion const &q)
{
    return {p[0] * q[0] - p[1] * q[1] - p[2] * q[2] - p[3] * q[3],
            p[0] * q[1] + p[1] * q[0] + p[2] * q[3] - p[3] * q[2],
            p[0] * q[2] - p[1] * q[3] + p[2] * q[0] + p[3] * q[1],
            p[0] * q[3] + p[1] * q[2] - p[2] * q[1] + p[3] * q[0]};
}

bool quaternion_real_compare(Quaternion const &p, Quaternion const &q)
{
    return p[0] < q[0];
}

int main()
{
    size_t b, n, m;
    int64_t d;
    cin >> b >> n >> d >> m;
    assert(b <= 3);
    vector<Quaternion> animals(n);

    switch (b)
    {
    case 1:
        for (Quaternion &q : animals)
        {
            cin >> q[0];
            q[1] = q[2] = q[3] = 0;
        }
        break;
    case 2:
        for (Quaternion &q : animals)
        {
            cin >> q[0] >> q[1];
            q[2] = q[3] = 0;
            q = quaternion_multiply(q, {1, 1, 0, 0});
        }
        break;
    case 3:
        for (Quaternion &q : animals)
        {
            cin >> q[0] >> q[1] >> q[2];
            q[3] = 0;
            q = quaternion_multiply(q, {1, 1, 1, 1});
        }
        break;
    }

    int64_t min_i = INT64_MAX, max_i = 0,
            min_j = INT64_MAX, max_j = 0,
            min_k = INT64_MAX, max_k = 0;

    for (Quaternion &q : animals)
    {
        min_i = min(min_i, q[1]), max_i = max(max_i, q[1]);
        min_j = min(min_j, q[2]), max_j = max(max_j, q[2]);
        min_k = min(min_k, q[3]), max_k = max(max_k, q[3]);
    }
    for (Quaternion &q : animals)
    {
        q[1] -= min_i, q[2] -= min_j, q[3] -= min_k;
    }
    max_i -= min_i, max_j -= min_j, max_k -= min_k;
    sort(animals.begin(), animals.end(), quaternion_real_compare);

    int64_t ans = 0;
    FenwickTree3d<int> tree({max_i + 1, max_j + 1, max_k + 1});
    auto it = animals.begin(), jt = animals.begin();

    while (it != animals.end())
    {
        while (jt != animals.end() && jt->at(0) <= it->at(0) + d)
        {
            tree.increment({jt->at(1), jt->at(2), jt->at(3)}, 1);
            jt++;
        }

        tree.increment({it->at(1), it->at(2), it->at(3)}, -1);
        ans += tree.range_sum({it->at(1) - d, it->at(2) - d, it->at(3) - d},
                              {it->at(1) + d, it->at(2) + d, it->at(3) + d});
        it++;
    }

    cout << ans << '\n';
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 3688 KB Output is correct
2 Correct 42 ms 3796 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 3420 KB Output is correct
2 Correct 53 ms 4288 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 3412 KB Output is correct
2 Correct 58 ms 4172 KB Output is correct
3 Correct 77 ms 4304 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 3412 KB Output is correct
2 Correct 51 ms 3420 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 3412 KB Output is correct
2 Correct 61 ms 4176 KB Output is correct
3 Correct 62 ms 4172 KB Output is correct
4 Correct 71 ms 4176 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 3932 KB Output is correct
2 Correct 93 ms 5080 KB Output is correct
3 Correct 81 ms 5096 KB Output is correct
4 Correct 92 ms 5072 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32484 KB Output is correct
2 Correct 14 ms 32468 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 3504 KB Output is correct
2 Correct 97 ms 3424 KB Output is correct
3 Correct 65 ms 3424 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 25004 KB Output is correct
2 Correct 257 ms 25000 KB Output is correct
3 Correct 106 ms 25004 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 45664 KB Output is correct
2 Correct 312 ms 45668 KB Output is correct
3 Correct 154 ms 45672 KB Output is correct