oj.uz

답안 #681820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681820 2023-01-14T13:38:13 Z finn__ Pairs (IOI07_pairs) C++17
30 / 100
 70 ms 5844 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);
        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] + 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;
    }
    case 3:
    {
        break;
    }
    }

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

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:73:51: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'long int' [-Wsign-compare]
   73 |             while (jt != animals.end() && *it + d >= *jt)
      |                                           ~~~~~~~~^~~~~~
pairs.cpp:97: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]
   97 |             while (jt != animals.end() && (*it)[0] + 2 * d >= (*jt)[0])

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1468 KB Output is correct
2 Correct 1 ms 1468 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1364 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 2260 KB Output is correct
2 Correct 35 ms 2516 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2132 KB Output is correct
2 Correct 41 ms 3108 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 2132 KB Output is correct
2 Correct 44 ms 2996 KB Output is correct
3 Correct 51 ms 3020 KB Output is correct

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 70 ms 5844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -