oj.uz

Submission #514853

# Submission time Handle Problem Language Result Execution time Memory
514853 2022-01-18T15:06:48 Z AugustinasJucas Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 892724 KB 
#include <bits/stdc++.h>
using namespace std;
const long long inf = 2.1e9 + 1;
const long long dydis = (3e5+1);
int n, m, v, ind;
long long x, y, kur, R;
int dbInd = 0, mInd = 0;
vector<int> allX;
vector<int> l, r, ml, mr;
vector<long long> treeVals;
vector<vector<long long> > base;
vector<pair<pair<int, int>, pair<int, long long> > > mas;
bitset<dydis> circleRemoved;
bitset<(4 * 21 * dydis)> removed;
vector<pair<int, int> > kurYra[dydis];
vector<int> rightmost;
vector<int> sz;
vector<int> tevas;
int by[dydis];
vector<int> unique(vector<int> &a) {
	vector<int> ret;
	sort(a.begin(), a.end());
	for(auto &x : a){
		if(ret.size() == 0 || ret.back() != x) ret.push_back(x); 
	}
	return ret;
}
int m1, m2;
void build(int v) {
	if(v >= m){
		l[v] = r[v] = dbInd++;
		ml[v] = mInd;
		for(auto x : base[l[v]]) {
			treeVals[mInd++] = x;
		}
		mr[v] = mInd-1;
	}else {
		build(v*2);
		build(v*2+1);
		
		l[v] = l[v*2];
		r[v] = r[v*2+1];
		ml[v] = mInd;
		
		m1 = ml[v*2];
		m2 = ml[v*2+1];
		while(true) {
			if(m1 == mr[v*2]+1 && m2 == mr[v*2+1]+1) break;
			if(m1 == mr[v*2]+1) {
				treeVals[mInd++] = treeVals[m2++];
			}else if(m2 == mr[v*2+1]+1){
				treeVals[mInd++] = treeVals[m1++];
			}else if(treeVals[m1] <= treeVals[m2]){
				treeVals[mInd++] = treeVals[m1++];
			}else {
				treeVals[mInd++] = treeVals[m2++];
			}
		}
		mr[v] = mInd-1;
	}
	for(int i = ml[v]; i <= mr[v]; i++) {
		kurYra[treeVals[i]%dydis].push_back({v, i});
	}
}
int vec[dydis]; 
int id = 0, ret;
int fP(int v) {
	id = 0;
	while(true) {
		vec[id++] = v;
		ret = v;
		if(tevas[v] == v) break;
		v = tevas[v];
	}
	for(int i = 0; i < id; i++) tevas[vec[i]] = ret;
	return ret;
}
void conn(int a, int b) {
	a = fP(a);
	b = fP(b);
	if(sz[a] < sz[b]) swap(a, b); 
	tevas[b] = a;
	sz[a] += sz[b];
	rightmost[a] = max(rightmost[a], rightmost[b]);
}
void remove(int ind){
	if(circleRemoved[ind]) return ;
	circleRemoved[ind] = 1;
	int i;
	for(auto &x : kurYra[ind]) {
		v = x.first;
		i = x.second;
		removed[i] = 1;
		if(i-1 >= ml[v] && removed[i-1]) {
			conn(i-1, i);
		}
		if(i+1 <= mr[v] && removed[i+1]) {
			conn(i+1, i);
		}
	}
}

void print(int v) {
	if(v < m){
		print(v*2);
		print(v*2+1);
	}
	cout << "v = " << v << ", [" << l[v] << "; " << r[v] << "], atitinkamas masyvas: ["; 
	for(int i = ml[v]; i <= mr[v]; i++) {
		if(removed[i]) continue;
		cout << "(y=" << treeVals[i]/dydis << ", i=" << treeVals[i]%dydis << ")";
		if(i != mr[v]) cout << ", ";
	}
	cout << "]\n";
}
long long X1, Y1, R1, X2, Y2, R2;
bool kertasi (int i, int j) {
	X1 = mas[i].second.first; Y1 = mas[i].second.second; R1 = mas[i].first.first;
	X2 = mas[j].second.first; Y2 = mas[j].second.second; R2 = mas[j].first.first;
	return (X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2) <= (R1 + R2) * (R1 + R2);
}
int beg;
bitset<dydis> selected;
int selList[dydis];
int selInd = 0;
void find(int v, int L, int R, long long down, long long up){
	if(L <= l[v] && r[v] <= R) {
		beg = lower_bound(treeVals.begin() + ml[v], treeVals.begin() + mr[v] + 1, 1ll * down * dydis) - treeVals.begin();
		for(int i = beg; i <= mr[v]; i++) {
			if(treeVals[i] / dydis > up) break;
			if(removed[i]) {
				i = rightmost[fP(i)];
				continue;
			}
			if(!selected[treeVals[i]%dydis]) {
				selected[treeVals[i]%dydis] = 1;
				selList[selInd++] = treeVals[i]%dydis;
			}
		}
		
	}else if(r[v] < L || R < l[v]) {
		
	}else{
		find(v*2, L, R, down, up);
		find(v*2+1, L, R, down, up);
	}
}
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	treeVals.resize(4 * 21 * dydis);
	l.resize(4 * dydis);
	r.resize(4 * dydis);
	ml.resize(4 * dydis);
	mr.resize(4 * dydis);
	rightmost.resize(4 * 21 * dydis);
	sz.resize(4 * 21 * dydis);
	tevas.resize(4 * 21 * dydis);
	for(int i = 0; i < (int) tevas.size(); i++) {
		tevas[i] = i;
		sz[i] = 1;
		rightmost[i] = i;
	}
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> x >> y >> R;
		y += inf;
		mas.push_back({{R, -i}, {x, y}});
	}
		
	sort(mas.begin(), mas.end());
	reverse(mas.begin(), mas.end());
	for(auto &x : mas) x.first.second *= -1;
	
	for(int i = 0; i < n; i++) {
		allX.push_back(mas[i].second.first-mas[i].first.first);
		allX.push_back(mas[i].second.first+mas[i].first.first);
	}
	allX = unique(allX);
	base.resize(allX.size());
	m = allX.size();
	
	for(int i = 0; i < n; i++) {
		x = mas[i].second.first;
		y = mas[i].second.second;
		R = mas[i].first.first;
		
		kur = lower_bound(allX.begin(), allX.end(), x+R) - allX.begin();
		base[kur].push_back(1ll*(y-R)*dydis + i);
		base[kur].push_back(1ll*(y+R)*dydis + i);
		
		kur = lower_bound(allX.begin(), allX.end(), x-R) - allX.begin();
		base[kur].push_back(1ll*(y-R)*dydis + i);
		base[kur].push_back(1ll*(y+R)*dydis + i);
	}
	
	for(auto &x : base) sort(x.begin(), x.end());
	
	build(1);
	long long L, R, ll, rr;
	for(int i = 0; i < n; i++) {
		if(circleRemoved[i]) continue;
		L = mas[i].second.first - mas[i].first.first;
		R = mas[i].second.first + mas[i].first.first;
		ll = lower_bound(allX.begin(), allX.end(), L) - allX.begin();
		rr = lower_bound(allX.begin(), allX.end(), R) - allX.begin();
		selInd = 0;
		find(1, ll, rr, mas[i].second.second - mas[i].first.first, mas[i].second.second + mas[i].first.first);
		for(int j = 0; j < selInd; j++){
			selected[selList[j]] = 0;
			if(!kertasi(i, selList[j])) continue;
			remove(selList[j]);
			by[mas[selList[j]].first.second] = mas[i].first.second;
		}
	}
	for(int i = 0; i < n; i++) {
		cout << by[i] + 1 << " ";
	}
	return 0;
}
/*
5
0 0 3
5 -2 2
5 0 1
1 1 1
1 -3 1

 11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1 
 
 

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 519420 KB Output is correct
2 Correct 211 ms 519412 KB Output is correct
3 Correct 220 ms 519284 KB Output is correct
4 Correct 207 ms 519252 KB Output is correct
5 Correct 206 ms 519432 KB Output is correct
6 Correct 209 ms 519336 KB Output is correct
7 Correct 213 ms 519340 KB Output is correct
8 Correct 223 ms 519412 KB Output is correct
9 Correct 206 ms 519392 KB Output is correct
10 Correct 226 ms 519352 KB Output is correct
11 Correct 220 ms 519288 KB Output is correct
12 Correct 224 ms 519404 KB Output is correct
13 Correct 206 ms 519364 KB Output is correct
14 Correct 215 ms 519376 KB Output is correct
15 Correct 208 ms 519344 KB Output is correct
16 Correct 216 ms 520020 KB Output is correct
17 Correct 230 ms 519992 KB Output is correct
18 Correct 227 ms 519964 KB Output is correct
19 Correct 235 ms 522924 KB Output is correct
20 Correct 239 ms 522960 KB Output is correct
21 Correct 236 ms 522920 KB Output is correct
22 Correct 235 ms 522740 KB Output is correct
23 Correct 250 ms 522712 KB Output is correct
24 Correct 230 ms 522648 KB Output is correct
25 Correct 242 ms 522728 KB Output is correct
26 Correct 235 ms 522680 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3116 ms 892724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 519236 KB Output is correct
2 Correct 1344 ms 638388 KB Output is correct
3 Execution timed out 3115 ms 874792 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3110 ms 874644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 519420 KB Output is correct
2 Correct 211 ms 519412 KB Output is correct
3 Correct 220 ms 519284 KB Output is correct
4 Correct 207 ms 519252 KB Output is correct
5 Correct 206 ms 519432 KB Output is correct
6 Correct 209 ms 519336 KB Output is correct
7 Correct 213 ms 519340 KB Output is correct
8 Correct 223 ms 519412 KB Output is correct
9 Correct 206 ms 519392 KB Output is correct
10 Correct 226 ms 519352 KB Output is correct
11 Correct 220 ms 519288 KB Output is correct
12 Correct 224 ms 519404 KB Output is correct
13 Correct 206 ms 519364 KB Output is correct
14 Correct 215 ms 519376 KB Output is correct
15 Correct 208 ms 519344 KB Output is correct
16 Correct 216 ms 520020 KB Output is correct
17 Correct 230 ms 519992 KB Output is correct
18 Correct 227 ms 519964 KB Output is correct
19 Correct 235 ms 522924 KB Output is correct
20 Correct 239 ms 522960 KB Output is correct
21 Correct 236 ms 522920 KB Output is correct
22 Correct 235 ms 522740 KB Output is correct
23 Correct 250 ms 522712 KB Output is correct
24 Correct 230 ms 522648 KB Output is correct
25 Correct 242 ms 522728 KB Output is correct
26 Correct 235 ms 522680 KB Output is correct
27 Correct 286 ms 526904 KB Output is correct
28 Correct 293 ms 526752 KB Output is correct
29 Correct 322 ms 526784 KB Output is correct
30 Correct 322 ms 526372 KB Output is correct
31 Correct 320 ms 526360 KB Output is correct
32 Correct 307 ms 526304 KB Output is correct
33 Correct 1174 ms 646036 KB Output is correct
34 Correct 1324 ms 645872 KB Output is correct
35 Correct 1269 ms 645060 KB Output is correct
36 Correct 1382 ms 640160 KB Output is correct
37 Correct 1385 ms 640192 KB Output is correct
38 Correct 1225 ms 640172 KB Output is correct
39 Correct 874 ms 581628 KB Output is correct
40 Correct 846 ms 581552 KB Output is correct
41 Correct 840 ms 581568 KB Output is correct
42 Correct 861 ms 581548 KB Output is correct
43 Correct 1072 ms 639884 KB Output is correct
44 Correct 1083 ms 639812 KB Output is correct
45 Correct 1101 ms 639776 KB Output is correct
46 Correct 1081 ms 639996 KB Output is correct
47 Correct 1077 ms 639808 KB Output is correct
48 Correct 1145 ms 640132 KB Output is correct
49 Correct 1057 ms 639852 KB Output is correct
50 Correct 1111 ms 639800 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 519420 KB Output is correct
2 Correct 211 ms 519412 KB Output is correct
3 Correct 220 ms 519284 KB Output is correct
4 Correct 207 ms 519252 KB Output is correct
5 Correct 206 ms 519432 KB Output is correct
6 Correct 209 ms 519336 KB Output is correct
7 Correct 213 ms 519340 KB Output is correct
8 Correct 223 ms 519412 KB Output is correct
9 Correct 206 ms 519392 KB Output is correct
10 Correct 226 ms 519352 KB Output is correct
11 Correct 220 ms 519288 KB Output is correct
12 Correct 224 ms 519404 KB Output is correct
13 Correct 206 ms 519364 KB Output is correct
14 Correct 215 ms 519376 KB Output is correct
15 Correct 208 ms 519344 KB Output is correct
16 Correct 216 ms 520020 KB Output is correct
17 Correct 230 ms 519992 KB Output is correct
18 Correct 227 ms 519964 KB Output is correct
19 Correct 235 ms 522924 KB Output is correct
20 Correct 239 ms 522960 KB Output is correct
21 Correct 236 ms 522920 KB Output is correct
22 Correct 235 ms 522740 KB Output is correct
23 Correct 250 ms 522712 KB Output is correct
24 Correct 230 ms 522648 KB Output is correct
25 Correct 242 ms 522728 KB Output is correct
26 Correct 235 ms 522680 KB Output is correct
27 Execution timed out 3116 ms 892724 KB Time limit exceeded
28 Halted 0 ms 0 KB -