oj.uz

답안 #396297

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396297 2021-04-29T17:26:35 Z Sorting Pairs (IOI07_pairs) C++17
45 / 100
 94 ms 11592 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
constexpr int N = 1e5 + 3;
constexpr int M[3] = {(int)(75e6 + 3), (int)(75e3 + 3), 75};

int b, n, d, m;
vector<int> a[N];
ll ans = 0;

struct Fenwick{
    int a[2 * M[1]];
    Fenwick(){}
    void update(int idx, int val){
        for(; idx < 2 * M[1]; idx += idx&-idx)
            a[idx] += val;
    }
    int query(int idx){
        int ret = 0;
        for(; idx >= 1; idx -= idx&-idx)
            ret += a[idx];
        return ret;
    }
    int query(int l, int r){
        return query(r) - query(l - 1);
    }
} f;

void solve_2(){
    for(int i = 0; i < n; ++i){
        int x = a[i][0], y = a[i][1];
        a[i][0] = x - y;
        a[i][1] = x + y;
    }
    sort(a, a + n);
    int l_ptr = 0, r_ptr = -1;
    for(int i = 0; i < n; ++i){
        while(a[l_ptr][0] < a[i][0] - d){
            f.update(a[l_ptr][1], -1);
            ++l_ptr;
        }
        while(r_ptr != n - 1 && a[r_ptr + 1][0] <= a[i][0] + d){
            ++r_ptr;
            f.update(a[r_ptr][1], 1);
        }
        ans += f.query(max(a[i][1] - d, 1), a[i][1] + d) - 1;
    }
    ans >>= 1;
}

void solve_1(){
    sort(a, a + n);
    int j = 0;
    for(int i = 0; i < n; ++i){
        while(j != n && a[j][0] <= a[i][0] + d)
            ++j;
        ans += j - i - 1;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> b >> n >> d >> m;
    for(int i = 0; i < n; ++i){
        a[i].resize(b);
        for(int j = 0; j < b; ++j)
            cin >> a[i][j];
    }

    if(b == 1) solve_1();
    else if(b == 2) solve_2();
    else assert(false);
    cout << ans << "\n";
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

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

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 5784 KB Output is correct
2 Correct 50 ms 5708 KB Output is correct
3 Correct 38 ms 5712 KB Output is correct

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Incorrect 4 ms 3148 KB Output isn't correct

Subtask #7
7.0 / 7.0

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

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 5820 KB Output is correct
2 Correct 64 ms 5788 KB Output is correct
3 Correct 58 ms 5816 KB Output is correct
4 Correct 63 ms 5824 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 6348 KB Output is correct
2 Incorrect 78 ms 6232 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 10.0

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