Submission #681818

#	Time	Username	Problem	Language	Result	Execution time	Memory
681818		finn__	Pairs (IOI07_pairs)	C++17	0 / 100	76 ms	7104 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()
{
    size_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);

        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] + 2 * d >= (*jt)[0])
            {
                tree.update((*jt)[1], 1);
                jt++;
            }
            ans += tree.query((*it)[1], (*it)[1] + 2 * d);
            tree.update((*it)[1], -1);
        }
        break;
    }
    }

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

Compilation message (stderr)

pairs.cpp: In function 'int main()':
pairs.cpp:72:51: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'long int' [-Wsign-compare]
   72 |             while (jt != animals.end() && *it + d >= *jt)
      |                                           ~~~~~~~~^~~~~~
pairs.cpp:96:60: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'std::array<long int, 2>::value_type' {aka 'long int'} [-Wsign-compare]
   96 |             while (jt != animals.end() && (*it)[0] + 2 * d >= (*jt)[0])

• Subtask 1: 0 / 6
• Subtask 2: 0 / 6
• Subtask 3: 0 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 6
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10