Submission #254361

#	Time	Username	Problem	Language	Result	Execution time	Memory
254361		shayan_p	Circle selection (APIO18_circle_selection)	C++14	100 / 100	1690 ms	661820 KiB

circle_selection

// And you curse yourself for things you never done
 
#include<bits/stdc++.h>
 
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
 
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef unsigned int ui;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
 
pair<pll, ll> p[maxn];
int arr[maxn], ans[maxn];
 
pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}
pll operator + (pll a, pll b){
    return {a.F + b.F, a.S + b.S};
}
ll operator ^ (pll a, pll b){
    return 1ll * a.F * b.F + 1ll * a.S * b.S;
}
bool ok(int i, int j){
    return 1ll * (p[j].S + p[i].S) * (p[j].S + p[i].S) >= ((p[i].F - p[j].F) ^ (p[i].F - p[j].F));
}

const int Log = 31;

struct node{
    node *nxt[2][2];
    vector<int> vec;
    node(){
	nxt[0][0] = nxt[0][1] = nxt[1][0] = nxt[1][1] = 0;
    }
};node* rt;

void add(int msk1, int msk2, int id){
    node* nw = rt;
    for(int i = Log-1; i >= 0; i--){
	nw->vec.PB(id);
	if(nw->nxt[bit(msk1, i)][bit(msk2, i)] == 0)
	    nw->nxt[bit(msk1, i)][bit(msk2, i)] = new node();
	nw = nw->nxt[bit(msk1, i)][bit(msk2, i)];
    }
    nw->vec.PB(id);
}

vector<node*> fnds;

void fnd(node* nw, ui l1, ui r1, ui l2, ui r2, ui L1 = 0, ui R1 = 1<<31, ui L2 = 0, ui R2 = 1<<31){
    if(r1 <= L1 || R1 <= l1 || r2 <= L2 || R2 <= l2)
	return;
    if(l1 <= L1 && R1 <= r1 && l2 <= L2 && R2 <= r2){
	fnds.PB(nw);
	return;
    }
    ui mid1 = (L1 + R1) >> 1;
    ui mid2 = (L2 + R2) >> 1;
    if(nw->nxt[0][0])
	fnd(nw->nxt[0][0], l1, r1, l2, r2, L1, mid1, L2, mid2);
    if(nw->nxt[0][1])
	fnd(nw->nxt[0][1], l1, r1, l2, r2, L1, mid1, mid2, R2);
    if(nw->nxt[1][0])
	fnd(nw->nxt[1][0], l1, r1, l2, r2, mid1, R1, L2, mid2);
    if(nw->nxt[1][1])
	fnd(nw->nxt[1][1], l1, r1, l2, r2, mid1, R1, mid2, R2);    	
}

int cnt[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    rt = new node();
	
    memset(ans, -1, sizeof ans);

    int n;    
    cin >> n;

    for(int i = 0; i < n; i++){
	cin >> p[i].F.F >> p[i].F.S >> p[i].S;
	p[i].F.F+= inf, p[i].F.S+= inf;
    }
    auto cmp = [](int i, int j){
		   return (p[i].S == p[j].S ? i > j : p[i].S < p[j].S);
	       };
    iota(arr, arr + n, 0);
    sort(arr, arr + n, cmp);
    
    for(int i = 0; i < n; i++){
	add(p[i].F.F, p[i].F.S, i);
    }
    
    int len = 0;
    
    for(int I = n-1; I >= 0; I--){
	int i = arr[I];
	while(Log > len && (1<<(Log-len-1)) >= p[i].S)
	    len++;
	if(ans[i] == -1){
	    ans[i] = i;
	    ll x = (p[i].F.F >> (Log - len)) << (Log - len), y = (p[i].F.S >> (Log-len)) << (Log - len), df = 1<<(Log-len);
	    fnds.clear();
	    fnd(rt, max(ll(0), x - 2ll * df), min(1ll<<Log, x + 3ll * df), max(ll(0), y - 2ll * df), min(1ll<<Log, y + 3ll * df));
	    for(node* nw : fnds){
		vector<int> vec;
		for(int id : nw->vec){
		    if(ans[id] == -1 && ok(id, i))
			ans[id] = i;
		    if(ans[id] == -1)
			vec.PB(id);//, assert(++cnt[id] <= 10);
		}
		nw->vec = vec;
	    }
	}
    }
    for(int i = 0; i < n; i++){
	cout << ans[i] + 1 << " ";
    }
    return cout << endl, 0;
}

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