Submission #387833

#	Time	Username	Problem	Language	Result	Execution time	Memory
387833		talant117408	Circle selection (APIO18_circle_selection)	C++17	12 / 100	1121 ms	47464 KiB

circle_selection

/*
    Code written by Talant I.D.
*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
 
int mod;
 
ll mode(ll a) {
    a %= mod;
    if (a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b) {
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b) {
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b) {
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b&1) res = ((res*a)%m+m)%m;
        a = ((a*a)%m+m)%m;
        b >>= 1;
    }
    return res;
}
  
void usaco(string s) {
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N = 3e5+7;
int removedBy[N];

int main() {
	do_not_disturb
    //~ usaco("marathon");
	
	int n;
	cin >> n;
	vector <int> x(n), y(n), R(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> R[i];
	}
	
	vector <pair <pii, pii>> points;
	for (int i = 0; i < n; i++) {
		points.pb(mp(mp(R[i], i+1), mp(x[i]-R[i], x[i]+R[i])));
	}
	
	auto cmp = [&](pair <pii, pii> a, pair <pii, pii> b) {
		if (a.first.first == b.first.first) return a.first.second < b.first.second;
		return a.first.first > b.first.first;
	};
	
	sort(all(points), cmp);
	
	//~ cout << endl;
	//~ for (auto to : points) cout << to.first.first << ' ' << to.first.second << ' ' << to.second.first << ' ' << to.second.second << endl;
	
	set <pii> byL, byR;
	for (auto to : points) byL.insert(mp(to.second.first, to.first.second));
	for (auto to : points) byR.insert(mp(to.second.second, to.first.second));
	
	for (auto to : points) {
		auto l = to.second.first, r = to.second.second;
		auto ind = to.first.second;
		if (removedBy[ind]) {
			continue;
		}
		auto it = byL.lb(mp(l, 0));
		while (it != byL.end() && (*it).first <= r) {
			removedBy[(*it).second] = ind;
			byR.erase(mp(x[(*it).second-1]+R[(*it).second-1], (*it).second));
			byL.erase(it);
			it = byL.lb(mp(l, 0));
		}
		//~ cout << sz(byL) << endl;
		auto it2 = byR.ub(mp(r, 2e9));
		while (it2 != byR.begin() && (*--it2).first >= l) {
			removedBy[(*it2).second] = ind;
			byL.erase(mp(x[(*it2).second-1]-R[(*it2).second-1], (*it2).second));
			byR.erase(it2);
			it2 = byR.ub(mp(r, 2e9));
		}
		//~ cout << ind << endl;
	}
	
	for (int i = 1; i <= n; i++) {
		cout << removedBy[i] << ' ';
	}
		
    return 0;
}
/*
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
*/

Compilation message (stderr)

circle_selection.cpp: In function 'void usaco(std::string)':
circle_selection.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   57 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
circle_selection.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13