Submission #1089594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089594		BLOBVISGOD	Pairs (IOI07_pairs)	C++17	100 / 100	124 ms	10332 KiB

pairs

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct fentree{
    vi a;
    fentree(int n) : a(n+1) {}
    void add(int i, int v){
        for(i++; i<sz(a); i+= i&(-i)) a[i]+=v;
    }

    // [0,r)
    int get(int r){
        int ans = 0;
        for(;r>0; r-=r&(-r)) ans += a[r];
        return ans;
    }
};

void trans(int& x, int& y, int B){
    int nx = x+y;
    y = B+y-x;
    x = nx;
}

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int b,n,d,m; cin >> b >> n >> d >> m;
    ll ans = 0;
    if (b==1){
        vi a(n);
        rep(i,0,n) cin >> a[i];
        sort(all(a)); 
        for(auto c : a){
            int lo = lower_bound(all(a),c-d)-begin(a);
            int hi = upper_bound(all(a),c+d)-begin(a); hi--;
            // one element is c itself, so closed interval counts;
            ans += max(0,hi-lo);
        }
    }else if (b==2){
        int B = 75005;

        struct event{
            // type 1 = add/remove, type 0 = update
            int x, y, mul, type;
            bool operator<(event b){
                return x<b.x or (x==b.x and type < b.type);
            }
        };
        int at = 0;
        vector<event> E(n*5);
        ans -= n;

        while(n--){
            int x,y; cin >> x >> y;
            trans(x,y,B);
            E[at++] = {x,y,1,0};
            E[at++] = {x+d,min(B*2,y+d+1),1,1}; // assume halfopen queries in fentree, closed in events
            E[at++] = {x-d-1,min(B*2,y+d+1),-1,1};
            E[at++] = {x+d,max(0,y-d),-1,1};
            E[at++] = {x-d-1,max(0,y-d),1,1};
        }

        fentree fen(B*2+1);

        sort(all(E));
        for(auto e : E){
            if (e.type==0){
                fen.add(e.y,e.mul);
            }else{
                ans += e.mul*fen.get(e.y);
            }
        }
    }else{
        int B = 77;
        vector<vector<vector<int>>> a(B+1,vvi(B*2+1,vi(B*2+1)));
        vector<array<int,3>> qs(n);
        rep(i,0,n) rep(j,0,3) cin >> qs[i][j];

        for(auto [x,y,z] : qs){
            trans(y,z,B);
            a[x][y][z]++;
        }

        rep(i,0,sz(a)) rep(j,0,sz(a[0])) rep(k,0,sz(a[0])-1) a[i][j][k+1] += a[i][j][k];
        rep(i,0,sz(a)) rep(j,0,sz(a[0])-1) rep(k,0,sz(a[0])) a[i][j+1][k] += a[i][j][k];

        auto get = [&](int x,int y, int z) -> int {
            x = max(0,min(x,B));
            y = max(0,min(y,B*2));
            z = max(0,min(z,B*2));
            return a[x][y][z];
        };

        for (auto [x,y,z] : qs){
            trans(y,z,B);
            rep(i,0,B){
                int nd = d-abs(x-i);
                if (nd<0) continue;
                ans += get(i,y+nd,z+nd) - get(i,y-nd-1,z+nd) - get(i,y+nd,z-nd-1) + get(i,y-nd-1,z-nd-1);
            }
            ans --;
        }
    }

    cout << ans/2 << '\n';
}

• 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