oj.uz

Submission #514776

# Submission time Handle Problem Language Result Execution time Memory
514776 2022-01-18T13:11:49 Z AugustinasJucas Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 879860 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
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 265 ms 509952 KB Output is correct
2 Correct 265 ms 509824 KB Output is correct
3 Correct 260 ms 510036 KB Output is correct
4 Correct 254 ms 509940 KB Output is correct
5 Correct 259 ms 509816 KB Output is correct
6 Correct 267 ms 510016 KB Output is correct
7 Correct 250 ms 509920 KB Output is correct
8 Correct 261 ms 510060 KB Output is correct
9 Correct 262 ms 509992 KB Output is correct
10 Correct 251 ms 509924 KB Output is correct
11 Correct 251 ms 509996 KB Output is correct
12 Correct 275 ms 509916 KB Output is correct
13 Correct 256 ms 509896 KB Output is correct
14 Correct 263 ms 509988 KB Output is correct
15 Correct 239 ms 509980 KB Output is correct
16 Correct 262 ms 510700 KB Output is correct
17 Correct 265 ms 510652 KB Output is correct
18 Correct 268 ms 510624 KB Output is correct
19 Correct 292 ms 513568 KB Output is correct
20 Correct 265 ms 513716 KB Output is correct
21 Correct 279 ms 513660 KB Output is correct
22 Correct 281 ms 513440 KB Output is correct
23 Correct 286 ms 513432 KB Output is correct
24 Correct 287 ms 513408 KB Output is correct
25 Correct 308 ms 513436 KB Output is correct
26 Correct 283 ms 513440 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 509924 KB Output is correct
2 Correct 1673 ms 630988 KB Output is correct
3 Execution timed out 3067 ms 864288 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 3087 ms 858196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 517272 KB Output is correct
2 Correct 318 ms 517284 KB Output is correct
3 Correct 314 ms 517272 KB Output is correct
4 Correct 338 ms 516868 KB Output is correct
5 Correct 305 ms 516976 KB Output is correct
6 Correct 301 ms 516812 KB Output is correct
7 Correct 1305 ms 636900 KB Output is correct
8 Correct 1350 ms 636808 KB Output is correct
9 Correct 1459 ms 635868 KB Output is correct
10 Correct 1495 ms 630584 KB Output is correct
11 Correct 1379 ms 630808 KB Output is correct
12 Correct 1429 ms 630736 KB Output is correct
13 Correct 1092 ms 571444 KB Output is correct
14 Correct 1066 ms 571408 KB Output is correct
15 Correct 1091 ms 571396 KB Output is correct
16 Correct 1256 ms 571572 KB Output is correct
17 Correct 1166 ms 630432 KB Output is correct
18 Correct 1207 ms 630316 KB Output is correct
19 Correct 1185 ms 630320 KB Output is correct
20 Correct 1228 ms 630376 KB Output is correct
21 Correct 1162 ms 630320 KB Output is correct
22 Correct 1213 ms 630608 KB Output is correct
23 Correct 1195 ms 630296 KB Output is correct
24 Correct 1249 ms 630304 KB Output is correct
25 Correct 265 ms 509952 KB Output is correct
26 Correct 265 ms 509824 KB Output is correct
27 Correct 260 ms 510036 KB Output is correct
28 Correct 254 ms 509940 KB Output is correct
29 Correct 259 ms 509816 KB Output is correct
30 Correct 267 ms 510016 KB Output is correct
31 Correct 250 ms 509920 KB Output is correct
32 Correct 261 ms 510060 KB Output is correct
33 Correct 262 ms 509992 KB Output is correct
34 Correct 251 ms 509924 KB Output is correct
35 Correct 251 ms 509996 KB Output is correct
36 Correct 275 ms 509916 KB Output is correct
37 Correct 256 ms 509896 KB Output is correct
38 Correct 263 ms 509988 KB Output is correct
39 Correct 239 ms 509980 KB Output is correct
40 Correct 262 ms 510700 KB Output is correct
41 Correct 265 ms 510652 KB Output is correct
42 Correct 268 ms 510624 KB Output is correct
43 Correct 292 ms 513568 KB Output is correct
44 Correct 265 ms 513716 KB Output is correct
45 Correct 279 ms 513660 KB Output is correct
46 Correct 281 ms 513440 KB Output is correct
47 Correct 286 ms 513432 KB Output is correct
48 Correct 287 ms 513408 KB Output is correct
49 Correct 308 ms 513436 KB Output is correct
50 Correct 283 ms 513440 KB Output is correct

Subtask #6
0 / 13.0

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