oj.uz

Submission #514781

# Submission time Handle Problem Language Result Execution time Memory
514781 2022-01-18T13:18:35 Z AugustinasJucas Circle selection (APIO18_circle_selection) C++14
37 / 100
 1678 ms 1048576 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;
}
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].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 282 ms 509924 KB Output is correct
2 Correct 266 ms 510040 KB Output is correct
3 Correct 302 ms 509916 KB Output is correct
4 Correct 366 ms 509820 KB Output is correct
5 Correct 275 ms 509996 KB Output is correct
6 Correct 301 ms 509928 KB Output is correct
7 Correct 281 ms 509900 KB Output is correct
8 Correct 320 ms 509928 KB Output is correct
9 Correct 269 ms 509908 KB Output is correct
10 Correct 317 ms 509980 KB Output is correct
11 Correct 275 ms 509968 KB Output is correct
12 Correct 287 ms 510004 KB Output is correct
13 Correct 312 ms 509916 KB Output is correct
14 Correct 281 ms 509940 KB Output is correct
15 Correct 337 ms 509984 KB Output is correct
16 Correct 279 ms 510692 KB Output is correct
17 Correct 315 ms 510656 KB Output is correct
18 Correct 319 ms 510608 KB Output is correct
19 Correct 291 ms 513636 KB Output is correct
20 Correct 303 ms 513672 KB Output is correct
21 Correct 372 ms 513656 KB Output is correct
22 Correct 367 ms 513372 KB Output is correct
23 Correct 335 ms 513392 KB Output is correct
24 Correct 300 ms 513392 KB Output is correct
25 Correct 274 ms 513336 KB Output is correct
26 Correct 339 ms 513440 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1576 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 509868 KB Output is correct
2 Correct 1678 ms 630900 KB Output is correct
3 Runtime error 1609 ms 1048576 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1550 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 517260 KB Output is correct
2 Correct 354 ms 517268 KB Output is correct
3 Correct 363 ms 517220 KB Output is correct
4 Correct 357 ms 516876 KB Output is correct
5 Correct 351 ms 516872 KB Output is correct
6 Correct 366 ms 516880 KB Output is correct
7 Correct 1359 ms 636872 KB Output is correct
8 Correct 1527 ms 636736 KB Output is correct
9 Correct 1520 ms 635940 KB Output is correct
10 Correct 1446 ms 630584 KB Output is correct
11 Correct 1525 ms 630704 KB Output is correct
12 Correct 1443 ms 630732 KB Output is correct
13 Correct 1060 ms 571416 KB Output is correct
14 Correct 1074 ms 571412 KB Output is correct
15 Correct 1093 ms 571396 KB Output is correct
16 Correct 947 ms 571360 KB Output is correct
17 Correct 1399 ms 630376 KB Output is correct
18 Correct 1384 ms 630320 KB Output is correct
19 Correct 1338 ms 630324 KB Output is correct
20 Correct 1463 ms 630364 KB Output is correct
21 Correct 1447 ms 630312 KB Output is correct
22 Correct 1390 ms 630500 KB Output is correct
23 Correct 1252 ms 630332 KB Output is correct
24 Correct 1583 ms 630304 KB Output is correct
25 Correct 282 ms 509924 KB Output is correct
26 Correct 266 ms 510040 KB Output is correct
27 Correct 302 ms 509916 KB Output is correct
28 Correct 366 ms 509820 KB Output is correct
29 Correct 275 ms 509996 KB Output is correct
30 Correct 301 ms 509928 KB Output is correct
31 Correct 281 ms 509900 KB Output is correct
32 Correct 320 ms 509928 KB Output is correct
33 Correct 269 ms 509908 KB Output is correct
34 Correct 317 ms 509980 KB Output is correct
35 Correct 275 ms 509968 KB Output is correct
36 Correct 287 ms 510004 KB Output is correct
37 Correct 312 ms 509916 KB Output is correct
38 Correct 281 ms 509940 KB Output is correct
39 Correct 337 ms 509984 KB Output is correct
40 Correct 279 ms 510692 KB Output is correct
41 Correct 315 ms 510656 KB Output is correct
42 Correct 319 ms 510608 KB Output is correct
43 Correct 291 ms 513636 KB Output is correct
44 Correct 303 ms 513672 KB Output is correct
45 Correct 372 ms 513656 KB Output is correct
46 Correct 367 ms 513372 KB Output is correct
47 Correct 335 ms 513392 KB Output is correct
48 Correct 300 ms 513392 KB Output is correct
49 Correct 274 ms 513336 KB Output is correct
50 Correct 339 ms 513440 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1577 ms 1048576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -