oj.uz

Submission #984736

# Submission time Handle Problem Language Result Execution time Memory
984736 2024-05-17T03:57:10 Z qwerasdfzxcl Circle selection (APIO18_circle_selection) C++17
0 / 100
 1056 ms 148104 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int INF = 1e9 + 100, CHK = 2;

struct Circle{
	int x, y, r, i, xl, xr;
	Circle(){}

	bool operator < (const Circle &C) const{
		if (r==C.r) return i < C.i;
		return r > C.r;
	}
}C[300300];
int ans[300300];

int ok(int i, int j){
	ll d = (ll)(C[i].x-C[j].x) * (C[i].x-C[j].x) + (ll)(C[i].y-C[j].y) * (C[i].y-C[j].y);
	ll r = (ll)(C[i].r + C[j].r) * (C[i].r + C[j].r);
	return d <= r;
}

struct Seg{

	int sz;
	map<int, int> tree[1201200];

	map<int, int>::iterator iter0[30], iter[30];
	int T[30], buf[30], pt, py = INF;

	void init(int n){
		sz = n;
	}

	void update(int l, int r, int y, int i){
		r++;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1){
				tree[l][y] = i;
				l++;
			}
			if (r&1){
				--r;
				tree[r][y] = i;
			}
		}
	}

	int queryU(int x, int y, int i){
		pt = 0;
		for (int node=x+sz;node>0;node>>=1){
			if (y!=py || T[pt] != node) iter0[pt] = tree[node].lower_bound(y);
			iter[pt] = iter0[pt];
			T[pt] = node;
			buf[pt] = (iter[pt]==tree[T[pt]].end())?INF:iter[pt]->first;
			pt++;
		}

		py = y;

		int ret = i;

		for (int _=0;_<CHK;_++){
			int idx = min_element(buf, buf+pt) - buf;
			if (buf[idx]==INF) break;
			if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);
			
			iter[idx]++;
			buf[idx] = (iter[idx]==tree[T[idx]].end())?INF:iter[idx]->first;
		}

		return ret;

	}

	int queryD(int i){
		for (int i=0;i<pt;i++){
			iter[i] = iter0[i];
			buf[i] = (iter[i]==tree[T[i]].begin())?(-INF):prev(iter[i])->first;
		}

		int ret = i;

		for (int _=0;_<CHK;_++){
			int idx = max_element(buf, buf+pt) - buf;
			if (buf[idx]==-INF) break;
			
			iter[idx]--;
			if (ok(i, iter[idx]->second)) ret = min(ret, iter[idx]->second);
			
			buf[idx] = (iter[idx]==tree[T[idx]].begin())?(-INF):prev(iter[idx])->first;
		}

		return ret;
	}
}tree;

int calc(int x, int i){
	int ret = i;
	ret = min(ret, tree.queryU(x, C[i].y, i));
	ret = min(ret, tree.queryD(i));

	return ret;
}

#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
static unsigned char str[40002000], *p=str;

int main(){
	fread(str, 1, 12002000, stdin);

	int n;
	rf(n);

	vector<int> X;
	for (int i=1;i<=n;i++){
		rf(C[i].x);
		rf(C[i].y);
		rf(C[i].r);
		X.push_back(C[i].x - C[i].r);
		X.push_back(C[i].x + C[i].r);

		C[i].i = i;
	}

	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	for (int i=1;i<=n;i++){
		C[i].xl = lower_bound(X.begin(), X.end(), C[i].x - C[i].r) - X.begin();
		C[i].xr = lower_bound(X.begin(), X.end(), C[i].x + C[i].r) - X.begin();
	}

	sort(C+1, C+n+1);
	tree.init(X.size());

	for (int i=1;i<=n;i++){
		ans[C[i].i] = min(calc(C[i].xl, i), calc(C[i].xr, i));
		if (ans[C[i].i]==i) tree.update(C[i].xl, C[i].xr, C[i].y, i);

		ans[C[i].i] = C[ans[C[i].i]].i;
	}

	for (int i=1;i<=n;i++) printf("%d ", ans[i]);
	printf("\n");
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:112:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |  fread(str, 1, 12002000, stdin);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59996 KB Output is correct
2 Correct 12 ms 59996 KB Output is correct
3 Correct 12 ms 60088 KB Output is correct
4 Correct 12 ms 60056 KB Output is correct
5 Correct 13 ms 60372 KB Output is correct
6 Correct 12 ms 59996 KB Output is correct
7 Correct 12 ms 59996 KB Output is correct
8 Incorrect 12 ms 59996 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 376 ms 78008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 59992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1056 ms 148104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59996 KB Output is correct
2 Correct 12 ms 59996 KB Output is correct
3 Correct 12 ms 60088 KB Output is correct
4 Correct 12 ms 60056 KB Output is correct
5 Correct 13 ms 60372 KB Output is correct
6 Correct 12 ms 59996 KB Output is correct
7 Correct 12 ms 59996 KB Output is correct
8 Incorrect 12 ms 59996 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59996 KB Output is correct
2 Correct 12 ms 59996 KB Output is correct
3 Correct 12 ms 60088 KB Output is correct
4 Correct 12 ms 60056 KB Output is correct
5 Correct 13 ms 60372 KB Output is correct
6 Correct 12 ms 59996 KB Output is correct
7 Correct 12 ms 59996 KB Output is correct
8 Incorrect 12 ms 59996 KB Output isn't correct
9 Halted 0 ms 0 KB -