oj.uz

Submission #599767

# Submission time Handle Problem Language Result Execution time Memory
599767 2022-07-19T20:38:46 Z gg123_pe Pairs (IOI07_pairs) C++14
100 / 100
 220 ms 27596 KB 
#include <bits/stdc++.h> 
using namespace std; 

typedef long long ll; 
typedef pair <pair<char,char>, pair<char,char>> T; 
#define f(i,a,b) for(ll i = a; i < b; i++)
#define fa(i,a,b) for(ll i = a; i >= b; i--)

const int N = 150005, M = 75001; 

int b, n, d, m, bit[N], c[76][155][155], s[76][155][155], t[76][155][155];
vector <vector <int>> a;
ll ans; 

void upd(int u, int val){
    for(; u < N; u = (u|(u+1))) bit[u] += val; 
}

int get(int u){
    int res = 0;
    for(; u >= 0; u = (u&(u+1)) - 1) res += bit[u];  
    return res;
}

int que(int l, int r){ return get(r) - get(l-1); }

int sum(int j, int x, int y, int r, int s){
    return t[j][r][s] + t[j][x-1][y-1] - t[j][r][y-1] - t[j][x-1][s];
}
int main(){
    cin >> b >> n >> d >> m; 

    a.resize(n); 

    f(i,0,n) {
        a[i].resize(b); 
        f(j,0,b) cin >> a[i][j];
    }

    if(b == 1){
        sort(a.begin(), a.end()); 

        int l = 0; 
        f(i,0,n){ 
            while(a[i][0] - a[l][0] > d) l++;
            ans += (ll) (i - l); 
        }
        cout << ans << "\n"; 
        return 0; 
    }
    if(b == 2){
        f(i,0,n){
            int u = a[i][0] + a[i][1], v = a[i][0] - a[i][1] + M; 
            a[i][0] = u, a[i][1] = v; 
        }
        sort(a.begin(), a.end()); 

        int l = 0; 
        f(i,0,n){
            while(a[i][0] - a[l][0] > d){
                upd(a[l][1], -1);
                l++; 
            }
            ans += (ll) que(max(0, a[i][1] - d), min(N-1, a[i][1]+d));
            upd(a[i][1], 1);
        }
        cout << ans << "\n"; 
        return 0; 
    }
   
    f(i,0,n){ 
        int u = a[i][1] + a[i][2], v = a[i][1] - a[i][2] + 76; 
        a[i][1] = u, a[i][2] = v; 
        c[a[i][0]][a[i][1]][a[i][2]]++; 
    }

    f(i,1,76){
        f(j,1,155) f(k,1,155) s[i][j][k] = s[i][j][k-1] + c[i][k][j];
        f(j,1,155) f(k,1,155) t[i][j][k] = t[i][j][k-1] + s[i][k][j];
    }
    f(i,0,n){
        f(j,1,76){
            if(abs(a[i][0] - j) > d) continue; 
            int dis = d - abs(a[i][0] - j);

            int f, g, h, w; 
            f = max(1, a[i][1]-dis); 
            g = max(1, a[i][2]-dis); 
            h = min(154, a[i][1]+dis); 
            w = min(154, a[i][2]+dis); 
            ans += (ll) sum(j, f, g, h, w); 
        }
        ans--; 
    }
    cout << ans/2 << "\n";
    return 0; 
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 5696 KB Output is correct
2 Correct 38 ms 5716 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 5756 KB Output is correct
2 Correct 54 ms 5708 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 5888 KB Output is correct
2 Correct 61 ms 5704 KB Output is correct
3 Correct 54 ms 5764 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 5680 KB Output is correct
2 Correct 59 ms 5776 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 5748 KB Output is correct
2 Correct 74 ms 5752 KB Output is correct
3 Correct 71 ms 5792 KB Output is correct
4 Correct 71 ms 5708 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6336 KB Output is correct
2 Correct 86 ms 6328 KB Output is correct
3 Correct 80 ms 6288 KB Output is correct
4 Correct 83 ms 6288 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 17256 KB Output is correct
2 Correct 17 ms 17216 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 20024 KB Output is correct
2 Correct 83 ms 20640 KB Output is correct
3 Correct 95 ms 20684 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 24264 KB Output is correct
2 Correct 215 ms 25184 KB Output is correct
3 Correct 120 ms 25160 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 26804 KB Output is correct
2 Correct 220 ms 27500 KB Output is correct
3 Correct 124 ms 27596 KB Output is correct