oj.uz

Submission #654559

# Submission time Handle Problem Language Result Execution time Memory
654559 2022-10-31T17:50:45 Z four_specks Pairs (IOI07_pairs) C++17
60 / 100
 48 ms 9024 KB 
#include <bits/stdc++.h>

using namespace std;

inline namespace
{
    template <typename T>
    struct PURS
    {
        PURS(int _n) : n(_n), tree(n + 1, 0) {}

        T sum(int l = 0) const { return sum(l, n); }

        T sum(int l, int r) const
        {
            T ret = 0;
            for (int k = r; k; k -= k & -k)
                ret += tree[k];
            for (int k = l; k; k -= k & -k)
                ret -= tree[k];

            return ret;
        }

        void add(int p, T t)
        {
            for (int k = p + 1; k <= n; k += k & -k)
                tree[k] += t;
        }

        int get(int p) const { return sum(p, p + 1); }
        void set(int p, T t) { add(p, t - get(p)); }

        int size() const { return n; }

    private:
        int n;
        vector<T> tree;
    };

} // 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)
    {
    }

    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 212 KB Output is correct
2 Correct 1 ms 316 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 19 ms 6476 KB Output is correct
2 Correct 21 ms 6580 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6996 KB Output is correct
2 Correct 28 ms 6940 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6948 KB Output is correct
2 Correct 27 ms 6996 KB Output is correct
3 Correct 25 ms 6988 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 37 ms 7948 KB Output is correct
2 Correct 34 ms 7888 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8104 KB Output is correct
2 Correct 35 ms 8012 KB Output is correct
3 Correct 35 ms 8096 KB Output is correct
4 Correct 41 ms 8020 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9024 KB Output is correct
2 Correct 39 ms 8980 KB Output is correct
3 Correct 37 ms 8976 KB Output is correct
4 Correct 44 ms 9004 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 6296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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