제출 #681821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681821		finn__	Pairs (IOI07_pairs)	C++17	60 / 100	72 ms	4168 KiB

pairs

#include <bits/stdc++.h>
using namespace std;

template <class T, int... ns>
struct FenwickTree
{
    T x = 0;

    void update(T v) { x += v; }
    T query() { return x; }
};

template <class T, int n, int... ns>
struct FenwickTree<T, n, ns...>
{

    FenwickTree<T, ns...> tree[n + 1];

    template <typename... Args>
    void update(int i, Args... args)
    {
        assert(i > 0);

        while (i <= n)
        {
            tree[i].update(args...);
            i += i & -i;
        }
    }

    template <typename... Args>
    T sum(int i, Args... args)
    {
        T x = 0;
        while (i)
        {
            x += tree[i].query(args...);
            i -= i & -i;
        }
        return x;
    }

    template <typename... Args>
    T query(int l, int r, Args... args)
    {
        if (!l)
            return sum(r, args...);
        return sum(r, args...) - sum(l - 1, args...);
    }
};

int main()
{
    int64_t b, n, d, m;
    cin >> b >> n >> d >> m;

    uint64_t ans = 0;

    switch (b)
    {
    case 1:
    {
        vector<int64_t> animals(n);
        for (int64_t &x : animals)
            cin >> x;
        sort(animals.begin(), animals.end());
        auto it = animals.begin();
        auto jt = upper_bound(animals.begin(), animals.end(), *it + d);
        ans = jt - it - 1;

        while (++it != animals.end())
        {
            while (jt != animals.end() && *it + d >= *jt)
                jt++;
            ans += jt - it - 1;
        }
        break;
    }
    case 2:
    {
        vector<array<int64_t, 2>> animals(n);
        for (auto &a : animals)
        {
            int64_t x, y;
            cin >> x >> y;
            a[0] = x - y;
            a[1] = x + y;
        }
        FenwickTree<int64_t, 150001> tree;
        sort(animals.begin(), animals.end());

        auto it = animals.begin();
        auto jt = animals.begin();

        while (it != animals.end())
        {
            while (jt != animals.end() && (*it)[0] + d >= (*jt)[0])
            {
                tree.update((*jt)[1], 1);
                jt++;
            }
            tree.update((*it)[1], -1);
            ans += tree.query(max<int64_t>(0, (*it)[1] - d), min<int64_t>((*it)[1] + d, 150000));
            it++;
        }
        break;
    }
    case 3:
    {
        break;
    }
    }

    cout << ans << '\n';
}

• 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