oj.uz

Submission #263804

# Submission time Handle Problem Language Result Execution time Memory
263804 2020-08-14T02:14:32 Z dsjong Circle selection (APIO18_circle_selection) C++14
12 / 100
 914 ms 60880 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define F first
#define S second
int ans[300005];
int x[300005], y[300005], r[300005];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	vector<pii>v;
	multiset<pii, greater<pii>>s1;
	multiset<pii>s2;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>r[i];
		v.push_back({r[i], -i});
		s1.insert({x[i]-r[i], i});
		s2.insert({x[i]+r[i], i});
	}
	sort(v.begin(), v.end());
	while(!v.empty()){
		int cur=-v.back().S;
		v.pop_back();
		if(ans[cur]) continue;
		int lb=x[cur]-r[cur], rb=x[cur]+r[cur];
		auto it=s2.lower_bound({lb, -1});
		while(it!=s2.end()){
			auto idx=it->S;
			if(x[idx]+r[idx]>rb) break;
			s2.erase(it++);
			if(ans[idx]) continue;
			ans[idx]=cur;
		}

		auto it1=s1.lower_bound({rb, 1e9});
		while(it1!=s1.end()){
			auto idx=it1->S;
			if(x[idx]-r[idx]<lb) break;
			s1.erase(it1++);
			if(ans[idx]) continue;
			ans[idx]=cur;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 54080 KB Output is correct
2 Correct 774 ms 54224 KB Output is correct
3 Correct 873 ms 60676 KB Output is correct
4 Correct 790 ms 60880 KB Output is correct
5 Correct 715 ms 58576 KB Output is correct
6 Correct 822 ms 58772 KB Output is correct
7 Correct 726 ms 58836 KB Output is correct
8 Correct 749 ms 58704 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -