Submission #686130

#	Time	Username	Problem	Language	Result	Execution time	Memory
686130		finn__	Pairs (IOI07_pairs)	C++17	100 / 100	377 ms	45672 KiB

pairs

#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 / 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