oj.uz

Submission #514788

# Submission time Handle Problem Language Result Execution time Memory
514788 2022-01-18T13:24:10 Z AugustinasJucas Circle selection (APIO18_circle_selection) C++14
37 / 100
 1404 ms 1045288 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[4*21*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 295 ms 509920 KB Output is correct
2 Correct 268 ms 509880 KB Output is correct
3 Correct 310 ms 509852 KB Output is correct
4 Correct 258 ms 509908 KB Output is correct
5 Correct 290 ms 509888 KB Output is correct
6 Correct 298 ms 510032 KB Output is correct
7 Correct 274 ms 509920 KB Output is correct
8 Correct 256 ms 509912 KB Output is correct
9 Correct 281 ms 509956 KB Output is correct
10 Correct 296 ms 509952 KB Output is correct
11 Correct 298 ms 509932 KB Output is correct
12 Correct 282 ms 509912 KB Output is correct
13 Correct 318 ms 509920 KB Output is correct
14 Correct 313 ms 509960 KB Output is correct
15 Correct 307 ms 509924 KB Output is correct
16 Correct 314 ms 510700 KB Output is correct
17 Correct 333 ms 510640 KB Output is correct
18 Correct 307 ms 510576 KB Output is correct
19 Correct 327 ms 513624 KB Output is correct
20 Correct 313 ms 513696 KB Output is correct
21 Correct 339 ms 513588 KB Output is correct
22 Correct 281 ms 513372 KB Output is correct
23 Correct 310 ms 513428 KB Output is correct
24 Correct 281 ms 513380 KB Output is correct
25 Correct 302 ms 513368 KB Output is correct
26 Correct 305 ms 513340 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1392 ms 1045288 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 260 ms 509892 KB Output is correct
2 Correct 1404 ms 628164 KB Output is correct
3 Runtime error 1299 ms 1040576 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 1196 ms 1044584 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 342 ms 517028 KB Output is correct
2 Correct 367 ms 516996 KB Output is correct
3 Correct 322 ms 516912 KB Output is correct
4 Correct 347 ms 516612 KB Output is correct
5 Correct 344 ms 516616 KB Output is correct
6 Correct 353 ms 516564 KB Output is correct
7 Correct 1205 ms 633888 KB Output is correct
8 Correct 1273 ms 633788 KB Output is correct
9 Correct 1377 ms 632932 KB Output is correct
10 Correct 1367 ms 628060 KB Output is correct
11 Correct 1300 ms 628072 KB Output is correct
12 Correct 1284 ms 628068 KB Output is correct
13 Correct 904 ms 570336 KB Output is correct
14 Correct 915 ms 570320 KB Output is correct
15 Correct 981 ms 570296 KB Output is correct
16 Correct 1012 ms 569848 KB Output is correct
17 Correct 1120 ms 627736 KB Output is correct
18 Correct 1124 ms 627716 KB Output is correct
19 Correct 1128 ms 627692 KB Output is correct
20 Correct 1082 ms 627804 KB Output is correct
21 Correct 1186 ms 627836 KB Output is correct
22 Correct 1102 ms 627920 KB Output is correct
23 Correct 1148 ms 627800 KB Output is correct
24 Correct 1256 ms 627696 KB Output is correct
25 Correct 295 ms 509920 KB Output is correct
26 Correct 268 ms 509880 KB Output is correct
27 Correct 310 ms 509852 KB Output is correct
28 Correct 258 ms 509908 KB Output is correct
29 Correct 290 ms 509888 KB Output is correct
30 Correct 298 ms 510032 KB Output is correct
31 Correct 274 ms 509920 KB Output is correct
32 Correct 256 ms 509912 KB Output is correct
33 Correct 281 ms 509956 KB Output is correct
34 Correct 296 ms 509952 KB Output is correct
35 Correct 298 ms 509932 KB Output is correct
36 Correct 282 ms 509912 KB Output is correct
37 Correct 318 ms 509920 KB Output is correct
38 Correct 313 ms 509960 KB Output is correct
39 Correct 307 ms 509924 KB Output is correct
40 Correct 314 ms 510700 KB Output is correct
41 Correct 333 ms 510640 KB Output is correct
42 Correct 307 ms 510576 KB Output is correct
43 Correct 327 ms 513624 KB Output is correct
44 Correct 313 ms 513696 KB Output is correct
45 Correct 339 ms 513588 KB Output is correct
46 Correct 281 ms 513372 KB Output is correct
47 Correct 310 ms 513428 KB Output is correct
48 Correct 281 ms 513380 KB Output is correct
49 Correct 302 ms 513368 KB Output is correct
50 Correct 305 ms 513340 KB Output is correct

Subtask #6
0 / 13.0

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