oj.uz

Submission #514795

# Submission time Handle Problem Language Result Execution time Memory
514795 2022-01-18T13:28:22 Z AugustinasJucas Circle selection (APIO18_circle_selection) C++14
37 / 100
 3000 ms 888300 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(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;
		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 277 ms 519256 KB Output is correct
2 Correct 247 ms 519364 KB Output is correct
3 Correct 240 ms 519356 KB Output is correct
4 Correct 259 ms 519400 KB Output is correct
5 Correct 233 ms 519204 KB Output is correct
6 Correct 244 ms 519320 KB Output is correct
7 Correct 234 ms 519424 KB Output is correct
8 Correct 248 ms 519316 KB Output is correct
9 Correct 256 ms 519308 KB Output is correct
10 Correct 270 ms 519364 KB Output is correct
11 Correct 265 ms 519396 KB Output is correct
12 Correct 251 ms 519420 KB Output is correct
13 Correct 240 ms 519364 KB Output is correct
14 Correct 247 ms 519328 KB Output is correct
15 Correct 292 ms 519376 KB Output is correct
16 Correct 257 ms 519952 KB Output is correct
17 Correct 253 ms 519952 KB Output is correct
18 Correct 245 ms 519976 KB Output is correct
19 Correct 267 ms 522896 KB Output is correct
20 Correct 271 ms 522884 KB Output is correct
21 Correct 258 ms 522904 KB Output is correct
22 Correct 285 ms 522716 KB Output is correct
23 Correct 281 ms 522668 KB Output is correct
24 Correct 277 ms 522780 KB Output is correct
25 Correct 278 ms 522720 KB Output is correct
26 Correct 295 ms 522608 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 519208 KB Output is correct
2 Correct 1514 ms 637556 KB Output is correct
3 Execution timed out 3090 ms 872384 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 3125 ms 871928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 526416 KB Output is correct
2 Correct 338 ms 526408 KB Output is correct
3 Correct 320 ms 526336 KB Output is correct
4 Correct 326 ms 526004 KB Output is correct
5 Correct 323 ms 526024 KB Output is correct
6 Correct 328 ms 526012 KB Output is correct
7 Correct 1343 ms 643204 KB Output is correct
8 Correct 1330 ms 643164 KB Output is correct
9 Correct 1429 ms 642328 KB Output is correct
10 Correct 1390 ms 637460 KB Output is correct
11 Correct 1342 ms 637420 KB Output is correct
12 Correct 1402 ms 637468 KB Output is correct
13 Correct 966 ms 579736 KB Output is correct
14 Correct 950 ms 579716 KB Output is correct
15 Correct 1055 ms 579688 KB Output is correct
16 Correct 1026 ms 579128 KB Output is correct
17 Correct 1228 ms 637172 KB Output is correct
18 Correct 1315 ms 637108 KB Output is correct
19 Correct 1285 ms 637088 KB Output is correct
20 Correct 1469 ms 637176 KB Output is correct
21 Correct 1273 ms 637156 KB Output is correct
22 Correct 1292 ms 637292 KB Output is correct
23 Correct 1228 ms 637052 KB Output is correct
24 Correct 1178 ms 637088 KB Output is correct
25 Correct 277 ms 519256 KB Output is correct
26 Correct 247 ms 519364 KB Output is correct
27 Correct 240 ms 519356 KB Output is correct
28 Correct 259 ms 519400 KB Output is correct
29 Correct 233 ms 519204 KB Output is correct
30 Correct 244 ms 519320 KB Output is correct
31 Correct 234 ms 519424 KB Output is correct
32 Correct 248 ms 519316 KB Output is correct
33 Correct 256 ms 519308 KB Output is correct
34 Correct 270 ms 519364 KB Output is correct
35 Correct 265 ms 519396 KB Output is correct
36 Correct 251 ms 519420 KB Output is correct
37 Correct 240 ms 519364 KB Output is correct
38 Correct 247 ms 519328 KB Output is correct
39 Correct 292 ms 519376 KB Output is correct
40 Correct 257 ms 519952 KB Output is correct
41 Correct 253 ms 519952 KB Output is correct
42 Correct 245 ms 519976 KB Output is correct
43 Correct 267 ms 522896 KB Output is correct
44 Correct 271 ms 522884 KB Output is correct
45 Correct 258 ms 522904 KB Output is correct
46 Correct 285 ms 522716 KB Output is correct
47 Correct 281 ms 522668 KB Output is correct
48 Correct 277 ms 522780 KB Output is correct
49 Correct 278 ms 522720 KB Output is correct
50 Correct 295 ms 522608 KB Output is correct

Subtask #6
0 / 13.0

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