Submission #654559

#	Time	Username	Problem	Language	Result	Execution time	Memory
654559		four_specks	Pairs (IOI07_pairs)	C++17	60 / 100	48 ms	9024 KiB

pairs

#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 / 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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10