oj.uz

Submission #681818

# Submission time Handle Problem Language Result Execution time Memory
681818 2023-01-14T13:34:11 Z finn__ Pairs (IOI07_pairs) C++17
0 / 100
 76 ms 7104 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()
{
    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

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.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 6.0

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

Subtask #6
0 / 7.0

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

Subtask #7
0 / 7.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 76 ms 7104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1480 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 1492 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 1492 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 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -