oj.uz

Submission #514773

# Submission time Handle Problem Language Result Execution time Memory
514773 2022-01-18T13:09:42 Z AugustinasJucas Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 878100 KB 
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int dydis = 3e5 + 1;
int n, m, v, ind;
int x, y, kur, R;
int dbInd = 0, mInd = 0;
vector<int> allX;
vector<int> l, r, ml, mr;
vector<pair<int, int> > treeVals;
vector<vector<pair<int, int> > > base;
vector<pair<pair<int, int>, pair<int, int> > > 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;
}

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;
		
		for(int i = ml[v*2]; i <= mr[v*2]; i++) {
			treeVals[mInd++] = treeVals[i];
		}
		for(int i = ml[v*2+1]; i <= mr[v*2+1]; i++) {
			treeVals[mInd++] = treeVals[i];
		}
		mr[v] = mInd-1;
		
		if(ml[v] < mr[v]) sort(treeVals.begin() + ml[v], treeVals.begin() + mr[v] + 1);
	}
	for(int i = ml[v]; i <= mr[v]; i++) {
		kurYra[treeVals[i].second].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].first << ", i=" << treeVals[i].second << ")";
		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, int down, int up){
	if(L <= l[v] && r[v] <= R) {
		beg = lower_bound(treeVals.begin() + ml[v], treeVals.begin() + mr[v] + 1, make_pair(down, -inf)) - treeVals.begin();
		for(int i = beg; i <= mr[v]; i++) {
			if(treeVals[i].first > up) break;
			if(removed[i]) {
				i = rightmost[fP(i)];
				continue;
			}
			if(!selected[treeVals[i].second]) {
				selected[treeVals[i].second] = 1;
				selList[selInd++] = treeVals[i].second;
			}
		}
		
	}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(2 * dydis);
	r.resize(2 * dydis);
	ml.resize(2 * dydis);
	mr.resize(2 * 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;
		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({y-R, i});
		base[kur].push_back({y+R, i});
		
		kur = lower_bound(allX.begin(), allX.end(), x-R) - allX.begin();
		base[kur].push_back({y-R, i});
		base[kur].push_back({y+R, i});
	}
	
	for(auto &x : base) sort(x.begin(), x.end());
	
	build(1);
	//cout << "po buildo" << endl;
	//cout << "mas:\n";
	//for(int i = 0; i < n; i++) {
	//	auto &x = mas[i];
	//	cout <<i << ". "  << "(" << x.second.first << ", " << x.second.second << "), r = " << x.first.first << endl;
	//}
	//cout << endl;
	
	//cout << "x-ai:\n";
	//for(int i = 0; i < m; i++) {
	//	cout << i << ". " << allX[i] << endl;
	//}
	//cout << endl;
	
	//print(1);
	
	//cout << endl;
	
	int 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;
		//cout << "Ieskau kvadratu, kurie kertasi su " << mas[i].first.second << "-uoju. ";
		find(1, ll, rr, mas[i].second.second - mas[i].first.first, mas[i].second.second + mas[i].first.first);
		//cout << "radau ";
		for(int j = 0; j < selInd; j++){
			selected[selList[j]] = 0;
			if(!kertasi(i, selList[j])) continue;
			//cout << mas[selList[j]].first.second << " ";
			remove(selList[j]);
			by[mas[selList[j]].first.second] = mas[i].first.second;
		}
		//cout << endl;
	}
	
	//cout << endl << endl << "ats: \n";
	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 244 ms 509916 KB Output is correct
2 Correct 268 ms 509904 KB Output is correct
3 Correct 240 ms 509920 KB Output is correct
4 Correct 259 ms 510012 KB Output is correct
5 Correct 266 ms 509884 KB Output is correct
6 Correct 243 ms 509916 KB Output is correct
7 Correct 255 ms 509964 KB Output is correct
8 Correct 288 ms 509904 KB Output is correct
9 Correct 268 ms 509920 KB Output is correct
10 Correct 252 ms 509916 KB Output is correct
11 Correct 247 ms 509924 KB Output is correct
12 Correct 248 ms 509980 KB Output is correct
13 Correct 238 ms 510004 KB Output is correct
14 Correct 276 ms 509920 KB Output is correct
15 Correct 266 ms 510016 KB Output is correct
16 Correct 258 ms 510684 KB Output is correct
17 Correct 261 ms 510568 KB Output is correct
18 Correct 241 ms 510616 KB Output is correct
19 Correct 310 ms 513684 KB Output is correct
20 Correct 277 ms 513652 KB Output is correct
21 Correct 283 ms 513644 KB Output is correct
22 Correct 287 ms 513384 KB Output is correct
23 Correct 293 ms 513436 KB Output is correct
24 Correct 306 ms 513492 KB Output is correct
25 Correct 308 ms 513340 KB Output is correct
26 Correct 325 ms 513496 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 509868 KB Output is correct
2 Correct 1671 ms 630932 KB Output is correct
3 Execution timed out 3134 ms 864624 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 3104 ms 858272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 509916 KB Output is correct
2 Correct 268 ms 509904 KB Output is correct
3 Correct 240 ms 509920 KB Output is correct
4 Correct 259 ms 510012 KB Output is correct
5 Correct 266 ms 509884 KB Output is correct
6 Correct 243 ms 509916 KB Output is correct
7 Correct 255 ms 509964 KB Output is correct
8 Correct 288 ms 509904 KB Output is correct
9 Correct 268 ms 509920 KB Output is correct
10 Correct 252 ms 509916 KB Output is correct
11 Correct 247 ms 509924 KB Output is correct
12 Correct 248 ms 509980 KB Output is correct
13 Correct 238 ms 510004 KB Output is correct
14 Correct 276 ms 509920 KB Output is correct
15 Correct 266 ms 510016 KB Output is correct
16 Correct 258 ms 510684 KB Output is correct
17 Correct 261 ms 510568 KB Output is correct
18 Correct 241 ms 510616 KB Output is correct
19 Correct 310 ms 513684 KB Output is correct
20 Correct 277 ms 513652 KB Output is correct
21 Correct 283 ms 513644 KB Output is correct
22 Correct 287 ms 513384 KB Output is correct
23 Correct 293 ms 513436 KB Output is correct
24 Correct 306 ms 513492 KB Output is correct
25 Correct 308 ms 513340 KB Output is correct
26 Correct 325 ms 513496 KB Output is correct
27 Correct 357 ms 517268 KB Output is correct
28 Correct 350 ms 517280 KB Output is correct
29 Correct 333 ms 517272 KB Output is correct
30 Correct 347 ms 516884 KB Output is correct
31 Correct 339 ms 516828 KB Output is correct
32 Correct 316 ms 516888 KB Output is correct
33 Correct 1481 ms 636908 KB Output is correct
34 Correct 1541 ms 636872 KB Output is correct
35 Correct 1473 ms 635980 KB Output is correct
36 Correct 1536 ms 630640 KB Output is correct
37 Correct 1518 ms 630716 KB Output is correct
38 Correct 1515 ms 630772 KB Output is correct
39 Correct 1118 ms 571428 KB Output is correct
40 Correct 1147 ms 571420 KB Output is correct
41 Correct 1115 ms 571400 KB Output is correct
42 Correct 1296 ms 571456 KB Output is correct
43 Correct 1134 ms 630448 KB Output is correct
44 Correct 1133 ms 630324 KB Output is correct
45 Correct 1191 ms 630480 KB Output is correct
46 Correct 1372 ms 630388 KB Output is correct
47 Correct 1207 ms 630324 KB Output is correct
48 Correct 1156 ms 630584 KB Output is correct
49 Correct 1379 ms 630300 KB Output is correct
50 Correct 1369 ms 630380 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 509916 KB Output is correct
2 Correct 268 ms 509904 KB Output is correct
3 Correct 240 ms 509920 KB Output is correct
4 Correct 259 ms 510012 KB Output is correct
5 Correct 266 ms 509884 KB Output is correct
6 Correct 243 ms 509916 KB Output is correct
7 Correct 255 ms 509964 KB Output is correct
8 Correct 288 ms 509904 KB Output is correct
9 Correct 268 ms 509920 KB Output is correct
10 Correct 252 ms 509916 KB Output is correct
11 Correct 247 ms 509924 KB Output is correct
12 Correct 248 ms 509980 KB Output is correct
13 Correct 238 ms 510004 KB Output is correct
14 Correct 276 ms 509920 KB Output is correct
15 Correct 266 ms 510016 KB Output is correct
16 Correct 258 ms 510684 KB Output is correct
17 Correct 261 ms 510568 KB Output is correct
18 Correct 241 ms 510616 KB Output is correct
19 Correct 310 ms 513684 KB Output is correct
20 Correct 277 ms 513652 KB Output is correct
21 Correct 283 ms 513644 KB Output is correct
22 Correct 287 ms 513384 KB Output is correct
23 Correct 293 ms 513436 KB Output is correct
24 Correct 306 ms 513492 KB Output is correct
25 Correct 308 ms 513340 KB Output is correct
26 Correct 325 ms 513496 KB Output is correct
27 Execution timed out 3085 ms 878100 KB Time limit exceeded
28 Halted 0 ms 0 KB -