oj.uz

답안 #685735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685735 2023-01-24T23:16:24 Z finn__ Pairs (IOI07_pairs) C++17
13 / 100
 308 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

private:
    ptrdiff_t get_index(array<ptrdiff_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<ptrdiff_t, 3> i) const
    {
        T x = 0;
        i[0]++, i[1]++, i[2]++;

        while (i[0])
        {
            ptrdiff_t u = i[1];
            while (u)
            {
                ptrdiff_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<ptrdiff_t, 3> i, array<ptrdiff_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<ptrdiff_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<ptrdiff_t, 3> i, T x)
    {
        i[0]++, i[1]++, i[2]++;

        while (i[0] <= n[0])
        {
            ptrdiff_t u = i[1];
            while (u <= n[1])
            {
                ptrdiff_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<ptrdiff_t, 4> Quaternion;

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

bool real_compare(Quaternion const &q1, Quaternion const &q2)
{
    return q1[0] < q2[0];
}

int main()
{
    size_t b, n, m;
    ptrdiff_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;
        }
        break;
    case 3:
        for (Quaternion &q : animals)
        {
            cin >> q[0] >> q[1] >> q[2];
            q[3] = 0;
        }
        break;
    }

    ptrdiff_t min_i = PTRDIFF_MAX, max_i = 0,
              min_j = PTRDIFF_MAX, max_j = 0,
              min_k = PTRDIFF_MAX, max_k = 0;
    for (Quaternion &q : animals)
    {
        q = rotate45(q);
        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(), 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) + 2 * 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 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 255 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 51 ms 7684 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 50 ms 7752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
7.0 / 7.0

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

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 62 ms 7656 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 66 ms 8024 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 32468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 4120 KB Output is correct
2 Incorrect 71 ms 4120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 220 ms 25892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 308 ms 46508 KB Output isn't correct
2 Halted 0 ms 0 KB -