Submission #681807

#	Time	Username	Problem	Language	Result	Execution time	Memory
681807		finn__	Pairs (IOI07_pairs)	C++17	30 / 100	621 ms	142556 KiB

pairs

#include <bits/stdc++.h>
using namespace std;

struct point2d
{
    int64_t x, y;

    bool operator<(point2d const &q) const
    {
        return x < q.x;
    }

    void rotate45()
    {
        x = x - y;
        y = x + y;
    }
};

int d;

bool event2d_compare(pair<point2d, bool> const &a, pair<point2d, bool> const &b)
{
    int64_t xa = a.second ? a.first.x : a.first.x + 2 * d,
            xb = b.second ? b.first.x : b.first.x + 2 * d;
    if (xa == xb)
        return a.second && !b.second;
    return xa < xb;
}

struct FenwickTree
{
    vector<uint64_t> t;

    FenwickTree(uint64_t n)
    {
        t = vector<uint64_t>(1 << (32 - __builtin_clz(n)), 0);
    }

    void increment(ptrdiff_t i)
    {
        i++;
        while (i <= t.size())
        {
            t[i - 1]++;
            i += i & -i;
        }
    }

    void decrement(ptrdiff_t i)
    {
        i++;
        while (i <= t.size())
        {
            t[i - 1]--;
            i += i & -i;
        }
    }

    uint64_t prefix_sum(ptrdiff_t i)
    {
        i++;
        uint64_t x = 0;
        while (i)
        {
            x += t[i - 1];
            i -= i & -i;
        }
        return x;
    }

    uint64_t range_sum(ptrdiff_t i, ptrdiff_t j)
    {
        if (j >= t.size())
            j = t.size() - 1;
        if (!i)
            return prefix_sum(j);
        return prefix_sum(j) - prefix_sum(i - 1);
    }
};

struct quaternion
{
    int64_t r, i, j, k;

    quaternion(int x, int y, int z)
    {
        r = x + y + z;
        i = x + y - z;
        j = x - y + z;
        k = x - y - z;
    }
};

bool event3d_cmp(pair<quaternion, bool> const &a, pair<quaternion, bool> const &b)
{
    int xa = a.second ? a.first.r : a.first.r + 2 * d,
        xb = b.second ? b.first.r : b.first.r + 2 * d;
    return xa == xb ? (a.second && !b.second) : xa < xb;
}

struct FenwickTree3d
{
    vector<vector<vector<uint64_t>>> t;

    FenwickTree3d(uint64_t n, uint64_t m, uint64_t l)
    {
        t = vector<vector<vector<uint64_t>>>(
            1 << (32 - __builtin_clz(n)), vector<vector<uint64_t>>(
                                              1 << (32 - __builtin_clz(m)), vector<uint64_t>(1 << (32 - __builtin_clz(l)), 0)));
    }

    void increment(ptrdiff_t i, ptrdiff_t j, ptrdiff_t k)
    {
        i++, j++, k++;
        while (i <= t.size())
        {
            ptrdiff_t u = j;
            while (u <= t[i - 1].size())
            {
                ptrdiff_t v = k;
                while (v <= t[i - 1][u - 1].size())
                {
                    t[i - 1][u - 1][v - 1]++;
                    v += v & -v;
                }
                u += u & -u;
            }
            i += i & -i;
        }
    }

    void decrement(ptrdiff_t i, ptrdiff_t j, ptrdiff_t k)
    {
        i++, j++, k++;
        while (i <= t.size())
        {
            ptrdiff_t u = j;
            while (u <= t[i - 1].size())
            {
                ptrdiff_t v = k;
                while (v <= t[i - 1][u - 1].size())
                {
                    t[i - 1][u - 1][v - 1]--;
                    v += v & -v;
                }
                u += u & -u;
            }
            i += i & -i;
        }
    }

    uint64_t prefix_sum(ptrdiff_t i, ptrdiff_t j, ptrdiff_t k)
    {
        i++, j++, k++;
        uint64_t x = 0;
        while (i)
        {
            ptrdiff_t u = j;
            while (u)
            {
                ptrdiff_t v = k;
                while (v)
                {
                    x += t[i - 1][u - 1][v - 1];
                    v -= v & -v;
                }
                u -= u & -u;
            }
            i -= i & -i;
        }

        return x;
    }

    uint64_t range_sum(
        ptrdiff_t i1, ptrdiff_t j1, ptrdiff_t k1,
        ptrdiff_t i2, ptrdiff_t j2, ptrdiff_t k2)
    {
        i2 = min<ptrdiff_t>(i2, t.size() - 1);
        j2 = min<ptrdiff_t>(j2, t[0].size() - 1);
        k2 = min<ptrdiff_t>(k2, t[0][0].size() - 1);

        uint64_t x = prefix_sum(i2, j2, k2);
        if (i1)
            x -= prefix_sum(i1 - 1, j2, k2);
        if (j1)
            x -= prefix_sum(i2, j1 - 1, k2);
        if (k1)
            x -= prefix_sum(i2, j2, k1 - 1);
        if (i1 && j1)
            x += prefix_sum(i1 - 1, j1 - 1, k2);
        if (i1 && k1)
            x += prefix_sum(i1 - 1, j2, k1 - 1);
        if (j1 && k1)
            x += prefix_sum(i2, j1 - 1, k1 - 1);
        if (i1 && j1 && k1)
            x -= prefix_sum(i1 - 1, j1 - 1, k1 - 1);
        return x;
    }
};

int main()
{
    int b;
    uint64_t n, m;
    cin >> b >> n >> d >> m;

    switch (b)
    {
    case 1:
    {
        vector<int64_t> animals(n);
        for (int64_t &x : animals)
            cin >> x;
        sort(animals.begin(), animals.end());
        auto it = animals.begin();
        auto jt = upper_bound(animals.begin(), animals.end(), *it + d);

        uint64_t total = jt - it - 1;
        while (++it != animals.end())
        {
            while (jt != animals.end() && *it + d >= *jt)
                jt++;
            total += jt - it - 1;
        }

        cout << total << '\n';
        break;
    }
    case 2:
    {
        vector<pair<point2d, bool>> animals;
        int64_t min_y = INT_MAX, max_y = INT_MIN;
        for (uint64_t i = 0; i < n; i++)
        {
            point2d p;
            cin >> p.x >> p.y;
            p.rotate45();
            animals.push_back({p, 1});
            animals.push_back({p, 0});
            min_y = min(min_y, p.y);
            max_y = max(max_y, p.y);
        }
        for (auto &[p, b] : animals)
            p.y -= min_y;
        max_y -= min_y;
        sort(animals.begin(), animals.end(), event2d_compare);
        uint64_t total = 0;

        FenwickTree tree(max_y + 1);
        for (auto const &[p, b] : animals)
        {
            if (b)
                tree.increment(p.y);
            else
            {
                tree.decrement(p.y);
                total += tree.range_sum(p.y, p.y + 2 * d);
            }
        }

        cout << total << '\n';
        break;
    }
    case 3:
    {
        vector<pair<quaternion, bool>> animals;
        int64_t min_i = INT_MAX, min_j = INT_MAX, min_k = INT_MAX,
                max_i = INT_MIN, max_j = INT_MIN, max_k = INT_MIN;
        for (uint64_t i = 0; i < n; i++)
        {
            int64_t x, y, z;
            cin >> x >> y >> z;
            animals.emplace_back(quaternion(x, y, z), 1);
            animals.emplace_back(quaternion(x, y, z), 0);

            min_i = min(min_i, animals.back().first.i);
            min_j = min(min_j, animals.back().first.j);
            min_k = min(min_k, animals.back().first.k);

            max_i = max(max_i, animals.back().first.i);
            max_j = max(max_j, animals.back().first.j);
            max_k = max(max_k, animals.back().first.k);
        }

        for (auto &[q, b] : animals)
        {
            q.i -= min_i;
            q.j -= min_j;
            q.k -= min_k;
        }
        max_i -= min_i, max_j -= min_j, max_k -= min_k;

        FenwickTree3d tree(max_i + 1, max_j + 1, max_k + 1);
        sort(animals.begin(), animals.end(), event3d_cmp);

        uint64_t total = 0;

        for (auto const &[q, b] : animals)
        {
            if (b)
            {
                tree.increment(q.i, q.j, q.k);
            }
            else
            {
                tree.decrement(q.i, q.j, q.k);
                total += tree.range_sum(q.i, q.j, q.k, q.i + 2 * d, q.j + 2 * d, q.k + 2 * d);
            }
        }

        cout << total << '\n';
        break;
    }
    }
}

Compilation message (stderr)

pairs.cpp: In member function 'void FenwickTree::increment(ptrdiff_t)':
pairs.cpp:43:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
pairs.cpp: In member function 'void FenwickTree::decrement(ptrdiff_t)':
pairs.cpp:53:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
pairs.cpp: In member function 'uint64_t FenwickTree::range_sum(ptrdiff_t, ptrdiff_t)':
pairs.cpp:74:15: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if (j >= t.size())
      |             ~~^~~~~~~~~~~
pairs.cpp: In member function 'void FenwickTree3d::increment(ptrdiff_t, ptrdiff_t, ptrdiff_t)':
pairs.cpp:116:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<std::vector<long unsigned int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
pairs.cpp:119:22: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             while (u <= t[i - 1].size())
      |                    ~~^~~~~~~~~~~~~~~~~~
pairs.cpp:122:26: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |                 while (v <= t[i - 1][u - 1].size())
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In member function 'void FenwickTree3d::decrement(ptrdiff_t, ptrdiff_t, ptrdiff_t)':
pairs.cpp:136:18: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<std::vector<long unsigned int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
pairs.cpp:139:22: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<std::vector<long unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |             while (u <= t[i - 1].size())
      |                    ~~^~~~~~~~~~~~~~~~~~
pairs.cpp:142:26: warning: comparison of integer expressions of different signedness: 'ptrdiff_t' {aka 'long int'} and 'std::vector<long unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |                 while (v <= t[i - 1][u - 1].size())
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10