Submission #599767

#	Time	Username	Problem	Language	Result	Execution time	Memory
599767		gg123_pe	Pairs (IOI07_pairs)	C++14	100 / 100	220 ms	27596 KiB

pairs

#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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10