Submission #599740

#	Time	Username	Problem	Language	Result	Execution time	Memory
599740		gg123_pe	Pairs (IOI07_pairs)	C++14	60 / 100	103 ms	7484 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];
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 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; 
    }
   
    cout << ans << "\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: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10