oj.uz

Submission #654596

# Submission time Handle Problem Language Result Execution time Memory
654596 2022-10-31T20:11:22 Z four_specks Pairs (IOI07_pairs) C++17
100 / 100
 309 ms 56368 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6100 KB Output is correct
2 Correct 18 ms 6100 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6196 KB Output is correct
2 Correct 22 ms 6100 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6208 KB Output is correct
2 Correct 27 ms 6196 KB Output is correct
3 Correct 22 ms 6196 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 980 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7340 KB Output is correct
2 Correct 32 ms 7344 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7344 KB Output is correct
2 Correct 36 ms 7360 KB Output is correct
3 Correct 38 ms 7364 KB Output is correct
4 Correct 36 ms 7336 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7916 KB Output is correct
2 Correct 41 ms 7856 KB Output is correct
3 Correct 39 ms 7884 KB Output is correct
4 Correct 38 ms 7864 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47316 KB Output is correct
2 Correct 27 ms 47340 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 8664 KB Output is correct
2 Correct 49 ms 9296 KB Output is correct
3 Correct 46 ms 9164 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 33064 KB Output is correct
2 Correct 203 ms 33952 KB Output is correct
3 Correct 90 ms 33772 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 55528 KB Output is correct
2 Correct 255 ms 56368 KB Output is correct
3 Correct 101 ms 56284 KB Output is correct