Submission #654596

#	Time	Username	Problem	Language	Result	Execution time	Memory
654596		four_specks	Pairs (IOI07_pairs)	C++17	100 / 100	309 ms	56368 KiB

pairs

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
    template <typename T, int Dim = 1>
    struct PURS
    {
        template <typename... Args>
        PURS(int _n, Args... args) : n(_n), tree(n + 1, PURS<T, Dim - 1>(args...)) {}

        template <typename... Args>
        T sum(int l, int r, Args... args) const
        {
            T ret = 0;
            for (int k = r; k; k -= k & -k)
                ret += tree[k].sum(args...);
            for (int k = l; k; k -= k & -k)
                ret -= tree[k].sum(args...);

            return ret;
        }

        template <typename... Args>
        void add(int p, Args... args)
        {
            for (int k = p + 1; k <= n; k += k & -k)
                tree[k].add(args...);
        }

    private:
        int n;
        vector<PURS<T, Dim - 1>> tree;
    };

    template <typename T>
    struct PURS<T, 0>
    {
        PURS() : val(0) {}

        T sum() const { return val; }
        void add(T t) { val += t; }

    private:
        T val;
    };

} // namespace

void solve()
{
    int b;
    int n;
    int m, d;
    cin >> b >> n >> d >> m;

    vector board(n, vector<int>(b));
    for (int i = 0; i < n; i++)
    {
        for (int &x : board[i])
            cin >> x, --x;
    }

    long cnt = 0;
    if (b == 1)
    {
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            a[i] = board[i][0];
        sort(a.begin(), a.end());

        for (int i = 0; i < n; i++)
            cnt += i - (lower_bound(a.begin(), a.end(), a[i] - d) - a.begin());
    }
    else if (b == 2)
    {
        vector<array<int, 2>> v(n), u(n);
        for (int i = 0; i < n; i++)
        {
            v[i] = {board[i][0], board[i][1]};
            u[i] = {v[i][0] - v[i][1], v[i][0] + v[i][1]};
        }
        sort(u.begin(), u.end());

        PURS<int> purs(2 * m - 1);
        for (int i = 0, j = 0; i < n; i++)
        {
            while (u[i][0] - u[j][0] > d)
            {
                purs.add(u[j][1], -1);
                j++;
            }

            cnt += purs.sum(max(0, u[i][1] - d), min(2 * m - 1, u[i][1] + d + 1));
            purs.add(u[i][1], 1);
        }
    }
    else if (b == 3)
    {
        vector<array<int, 3>> v(n);
        vector<array<int, 4>> u(n);
        for (int i = 0; i < n; i++)
        {
            v[i] = {board[i][0], board[i][1], board[i][2]};
            u[i] = {
                v[i][0] - v[i][1] - v[i][2],
                v[i][0] - v[i][1] + v[i][2] + m - 1,
                v[i][0] + v[i][1] - v[i][2] + m - 1,
                v[i][0] + v[i][1] + v[i][2]};
        }
        sort(u.begin(), u.end());

        PURS<int, 3> purs(3 * m - 1, 3 * m - 1, 3 * m - 1);
        for (int i = 0, j = 0; i < n; i++)
        {
            while (u[i][0] - u[j][0] > d)
            {
                purs.add(u[j][1], u[j][2], u[j][3], -1);
                j++;
            }

            cnt +=
                purs.sum(
                    max(0, u[i][1] - d), min(3 * m - 1, u[i][1] + d + 1),
                    max(0, u[i][2] - d), min(3 * m - 1, u[i][2] + d + 1),
                    max(0, u[i][3] - d), min(3 * m - 1, u[i][3] + d + 1));
            purs.add(u[i][1], u[i][2], u[i][3], 1);
        }
    }

    cout << cnt << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

• 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