oj.uz

Submission #654587

# Submission time Handle Problem Language Result Execution time Memory
654587 2022-10-31T19:40:18 Z four_specks Pairs (IOI07_pairs) C++17
60 / 100
 61 ms 9012 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);
        for (int i = 0; i < n; i++)
            v[i] = {board[i][0], board[i][1]};

        vector<array<int, 2>> u(n);
        for (int i = 0; i < n; i++)
            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)
    {
        // for (int i = 0; i < n; i++)
        // {
        // }
    }

    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 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6564 KB Output is correct
2 Correct 23 ms 6588 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6936 KB Output is correct
2 Correct 29 ms 6952 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6860 KB Output is correct
2 Correct 39 ms 6868 KB Output is correct
3 Correct 30 ms 6868 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 40 ms 7932 KB Output is correct
2 Correct 47 ms 7936 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8236 KB Output is correct
2 Correct 39 ms 8128 KB Output is correct
3 Correct 46 ms 8120 KB Output is correct
4 Correct 39 ms 8116 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 8752 KB Output is correct
2 Correct 45 ms 9012 KB Output is correct
3 Correct 43 ms 8984 KB Output is correct
4 Correct 51 ms 8992 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 6304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 6504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -