oj.uz

Submission #501743

# Submission time Handle Problem Language Result Execution time Memory
501743 2022-01-04T12:39:59 Z stefantaga Pairs (IOI07_pairs) C++14
100 / 100
 270 ms 14048 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
 
using namespace std;
 
typedef long long ll;
constexpr int N = 1e5 + 3;
constexpr int M[3] = {(int)(75e6 + 3), (int)(75e3 + 3), 75 + 3};
 
int b, n, d, m, t[M[2]][2 * M[2]][2 * M[2]];
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;
 
int get_cnt(int idx, int x1, int y1, int x2, int y2){
    x1 = max(x1, 1), y1 = max(y1, 1);
    x2 = min(x2, 2 * M[2] - 1), y2 = min(y2, 2 * M[2] - 1);
    return t[idx][x2][y2] - t[idx][x2][y1 - 1] - t[idx][x1 - 1][y2] + t[idx][x1 - 1][y1 - 1];
}
 
void solve_3(){
    for(int i = 0; i < n; ++i){
        int x = a[i][1], y = a[i][2];
        a[i][1] = x - y + M[2];
        a[i][2] = x + y;
        t[a[i][0]][a[i][1]][a[i][2]]++;
    }
    for(int i = 0; i < M[2]; ++i){
        for(int j = 1; j < 2 * M[2]; ++j)
            for(int k = 1; k < 2 * M[2]; ++k)
                t[i][j][k] += t[i][j][k - 1] + t[i][j - 1][k] - t[i][j - 1][k - 1];
    }
    for(int i = 0; i < n; ++i){
        for(int dist = 0; dist <= d; ++dist){
            int rem = d - dist;
            if(a[i][0] - dist >= 1)
                ans += get_cnt(a[i][0] - dist, a[i][1] - rem, a[i][2] - rem, a[i][1] + rem, a[i][2] + rem);
            if(!dist) continue;
            if(a[i][0] + dist <= m)
                ans += get_cnt(a[i][0] + dist, a[i][1] - rem, a[i][2] - rem, a[i][1] + rem, a[i][2] + rem);
        }
        --ans;
    }
    ans >>= 1;
}
 
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), min(a[i][1] + d, 2 * M[1] - 1)) - 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 solve_3();
    cout << ans << "\n";
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6128 KB Output is correct
2 Correct 36 ms 6152 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5708 KB Output is correct
2 Correct 34 ms 5712 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5772 KB Output is correct
2 Correct 44 ms 5744 KB Output is correct
3 Correct 43 ms 5708 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3332 KB Output is correct
2 Correct 3 ms 3276 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 6316 KB Output is correct
2 Correct 53 ms 6324 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6532 KB Output is correct
2 Correct 54 ms 6532 KB Output is correct
3 Correct 51 ms 6536 KB Output is correct
4 Correct 58 ms 6500 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7392 KB Output is correct
2 Correct 58 ms 7488 KB Output is correct
3 Correct 52 ms 7460 KB Output is correct
4 Correct 49 ms 7404 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10060 KB Output is correct
2 Correct 8 ms 10136 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13768 KB Output is correct
2 Correct 42 ms 13820 KB Output is correct
3 Correct 49 ms 13824 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13996 KB Output is correct
2 Correct 169 ms 14040 KB Output is correct
3 Correct 83 ms 14020 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 14004 KB Output is correct
2 Correct 270 ms 14048 KB Output is correct
3 Correct 93 ms 13944 KB Output is correct