Submission #1141798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141798		Math4Life2020	Circle selection (APIO18_circle_selection)	C++20	64 / 100	2422 ms	1114112 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; using ui = __int128;

const ll Nm = 3e5+5; const ll E = 32;
set<pii> sact; //{-rad,indx}
vector<ll> vget; //vector of indices you are getting
ll ans[Nm];
ll x[Nm];
ll y[Nm];
ll r[Nm];

struct Node {
    unordered_set<ll> selem;
    ll xc;
    ll yc;
    ll ec;
    Node* cld[2][2];
    Node(ll _xc, ll _yc, ll _ec, vector<ll> _ve) {
        cld[0][0]=nullptr;
        cld[0][1]=nullptr;
        cld[1][0]=nullptr;
        cld[1][1]=nullptr;
        for (ll x0: _ve) {
            selem.insert(x0);
        }
        xc = _xc;
        yc = _yc;
        ec = _ec;
       // cout << "created node with xc,yc,ec="<<xc<<","<<yc<<","<<ec<<"\n";
    }
    void pdn(ll e0) {
        if (e0<ec) {
            for (ll i=0;i<2;i++) {
                for (ll j=0;j<2;j++) {
                    if (cld[i][j]!=nullptr) {
                        cld[i][j]->pdn(e0);
                    }
                }
            }
            return;
        }
        vector<ll> vpd[2][2];
        for (ll i: selem) {
           // cout << "new eval = "<<(ec-1)<<"\n";
            //cout << "ymod val: y="<<y[i]<<"\n";
            //cout << "div result: "<<(y[i]>>(ec-1))<<"\n";
            vpd[(x[i]>>(ec-1))%2][(y[i]>>(ec-1))%2].push_back(i);
        }
        for (ll i=0;i<2;i++) {
            for (ll j=0;j<2;j++) {
                if (!vpd[i][j].empty()) {
                    cld[i][j]= new Node(2*xc+i,2*yc+j,ec-1,vpd[i][j]);
                }
            }
        }
    }
    void get(ll x0, ll y0, ll e0) {
       // cout << "get: x0,y0,e0="<<x0<<","<<y0<<","<<e0<<"\n";
        //cout << "at: xc,yc,ec="<<xc<<","<<yc<<","<<ec<<"\n";
        if (e0==ec) {
            if (x0==xc && y0==yc) {
                for (ll x1: selem) {
                    //cout << "push back!\n";
                    vget.push_back(x1);
                }
            }
        } else {
            assert(ec>e0);
            //cout << (x0>>(ec-e0)) << " = test val \n";
            if ((x0>>(ec-e0))==xc && (y0>>(ec-e0))==yc) {
                for (ll i=0;i<2;i++) {
                    for (ll j=0;j<2;j++) {
                        if (cld[i][j]!=nullptr) {
                            cld[i][j]->get(x0,y0,e0);
                        }
                    }
                }
            }
        }
    }
    void del(ll x0, ll y0, ll e0, ll j) {
        if (e0<ec) {
            assert(cld[(x0>>(ec-1))%2][(y0>>(ec-1))%2]!=nullptr);
            cld[(x0>>(ec-1))%2][(y0>>(ec-1))%2]->del(x0,y0,e0,j);
        } else {
            selem.erase(j);
        }
    }
};

inline ll l2(ll x) {
    return (63LL-__builtin_clzll(x));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    vector<ll> vi0;
    for (ll i=0;i<N;i++) {
        cin >> x[i] >> y[i] >> r[i];
        x[i]+=((ll)1e9);
        y[i]+=((ll)1e9);
        sact.insert({-r[i],i});
        vi0.push_back(i);
    }
    ll EC = E;
    Node* rt = new Node(0,0,E,vi0);
    while (sact.size()!=0) {
        auto A0 = *sact.begin();
        ll i = A0.second;
        ll L = 2+l2(2*r[i]+1);
        while (L<EC) {
            rt->pdn(EC);
            EC--;
        }
        vget.clear();
        ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
        ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
       // cout << "nx,ny,L="<<nx<<","<<ny<<","<<L<<"\n";
        assert(x[i]>=(nx<<L));
        assert(x[i]<((nx+2)<<L));
        assert(y[i]>=(ny<<L));
        assert(y[i]<((ny+2)<<L));
        rt->get(nx,ny,L);
        rt->get(nx,ny+1,L);
        rt->get(nx+1,ny,L); 
        rt->get(nx+1,ny+1,L);
        //exit(0);
        assert(vget.size()!=0);
        for (ll j: vget) {
            ui dx = (x[j]-x[i]); dx = dx*dx;
            ui dy = (y[j]-y[i]); dy = dy*dy;
            ui dr = (r[i]+r[j]); dr = dr*dr;
            if ((dx+dy)<=dr) {
                ans[j]=i+1;
                sact.erase(sact.find({-r[j],j}));
                rt->del((x[j]),(y[j]),L,j);
            }
        }
    }
    for (ll i=0;i<N;i++) {
        cout << ans[i];
        if (i!=(N-1)) {
            cout << " ";
        }
    }
    cout << "\n";
}

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 30 / 30
• Subtask 6: 0 / 13