oj.uz

답안 #762739

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
762739 2023-06-21T17:21:26 Z caganyanmaz Pairs (IOI07_pairs) C++17
18 / 100
 228 ms 46244 KB 
#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
using namespace std;


struct SegTree
{
        int n;
        vector<int> data, left, right;
        SegTree(int n) : n(n), data(1, 0), left(1, -1), right(1, -1) {}
        void cc(int index)
        {
                if (left[index] == -1)
                {
                        left[index] = data.size();
                        data.pb(0);
                        left.pb(-1);
                        right.pb(-1);
                }
                if (right[index] == -1)
                {
                        right[index] = data.size();
                        data.pb(0);
                        left.pb(-1);
                        right.pb(-1);
                }
        }
        void update(int l, int r, int index, int i, int val)
        {
                if (i >= r || l > i)
                        return;
                if (l + 1 == r)
                {
                        data[index] += val;
                        return;
                }
                cc(index);
                int m = l+r>>1;
                update(l, m, left[index], i, val);
                update(m, r, right[index], i, val);
                data[index] = data[left[index]] + data[right[index]];
        }
        int get(int l, int r, int index, int ss, int ee)
        {
                if (ss >= r || l >= ee)
                        return 0;
                if (ee >= r && l >= ss)
                        return  data[index];
                int m = l+r>>1;
                int lres = 0, rres = 0;
                if (left[index] != -1)
                        lres = get(l, m, left[index], ss, ee);
                if (right[index] != -1)
                        rres = get(m, r, right[index], ss, ee);
                return lres + rres;
        }
        void update(int i, int val) { update(0, n, 0, i, val ); }
        int get(int ss, int ee) { return get(0, n, 0, ss, ee); }
};

void solve1d()
{
        int n, d, m;
        cin >> n >> d >> m;
        SegTree st(m);
        vector<int> v(n);
        for (int& i : v)
        {
                cin >> i;
                st.update(i, 1);
        }
        int encounters = 0;
        for (int i : v)
        {
                int l_bound = max(i-d, static_cast<int>(0));
                int r_bound = min(i+d+1, m);
                encounters += st.get(l_bound, r_bound) - 1;
        }
        assert(encounters % 2 == 0);
        cout << (encounters / 2) << "\n";
}

int32_t main()
{
        int b;
        cin >> b;
        assert(b == 1);
        solve1d();
}

Compilation message

pairs.cpp: In member function 'void SegTree::update(int64_t, int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:39:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |                 int m = l+r>>1;
      |                         ~^~
pairs.cpp: In member function 'int64_t SegTree::get(int64_t, int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:50:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |                 int m = l+r>>1;
      |                         ~^~

Subtask #1
0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 46140 KB Output is correct
2 Correct 88 ms 9340 KB Output is correct
3 Correct 68 ms 2408 KB Output is correct

Subtask #6
0 / 7.0

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

Subtask #7
0 / 7.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 8.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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