oj.uz

Submission #681821

# Submission time Handle Problem Language Result Execution time Memory
681821 2023-01-14T13:55:42 Z finn__ Pairs (IOI07_pairs) C++17
60 / 100
 72 ms 4168 KB 
#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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2260 KB Output is correct
2 Correct 24 ms 2256 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2132 KB Output is correct
2 Correct 63 ms 2144 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2260 KB Output is correct
2 Correct 44 ms 2236 KB Output is correct
3 Correct 40 ms 2260 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1484 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 3028 KB Output is correct
2 Correct 48 ms 3532 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3028 KB Output is correct
2 Correct 61 ms 3796 KB Output is correct
3 Correct 56 ms 3668 KB Output is correct
4 Correct 64 ms 3784 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3028 KB Output is correct
2 Correct 72 ms 4168 KB Output is correct
3 Correct 68 ms 4052 KB Output is correct
4 Correct 69 ms 4032 KB Output is correct

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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