Submission #745064

#	Time	Username	Problem	Language	Result	Execution time	Memory
745064		b00norp	Circle selection (APIO18_circle_selection)	C++14	0 / 100	767 ms	1048576 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 1e18, N = 3e5 + 5;

bool cmp(array<int, 3> a, array<int, 3> b)
{
	if(a[0] != b[0])
	{
		return a[0] > b[0];
	}
	return a[1] < b[1];
}

struct node
{
	node *left_child, *right_child;
	int value, l, r;

	node(int x, int ll, int rr)
	{
		left_child = NULL;
		right_child = NULL;
		value = x;
		l = ll;
		r = rr;
	}
	node(int ll, int rr)
	{
		left_child = NULL;
		right_child = NULL;
		value = INF;
		l = ll;
		r = rr;
	}
} *root;

void Update(node *cur, int ql, int qr, int qval)
{
	if(ql <= cur->l && cur->r <= qr)
	{
		cur->value = qval;
		return;
	}
	if(ql > cur->r || qr < cur->l)
	{
		return;
	}
	int mid = (cur->l + cur->r) / 2;
	if(cur->left_child == NULL)
	{
		cur->left_child = new node(cur->l, mid);
	}
	if(cur->right_child == NULL)
	{
		cur->right_child = new node(mid + 1, cur->r);
	}
	Update(cur->left_child, ql, qr, qval);
	Update(cur->right_child, ql, qr, qval);
}

int Query(node *cur, int qpos)
{
	if(cur->value != INF)
	{
		return cur->value;
	}
	if(cur->l == cur->r)
	{
		return cur->value;
	}
	int mid = (cur->l + cur->r) / 2;
	if(qpos <= mid)
	{
		if(cur->left_child == NULL)
		{
			return cur->value;
		}
		return Query(cur->left_child, qpos);
	}
	if(cur->right_child == NULL)
	{
		return cur->value;
	}
	return Query(cur->right_child, qpos);
}

void Solve() 
{
	int n;
	cin >> n;
	root = new node(-1e9, 1e9);
	vector<array<int, 3> > circle(n + 1);
	for(int i = 1; i <= n; i++)
	{
		cin >> circle[i][0] >> circle[i][1] >> circle[i][2];
	}
	vector<array<int, 3> > order;
	for(int i = 1; i <= n; i++)
	{
		order.push_back({circle[i][2], i, circle[i][0]});
	}
	sort(order.begin(), order.end(), cmp);
	reverse(order.begin(), order.end());
	for(auto [radius, idx, x]: order)
	{
		Update(root, x, x, idx);
	}
	reverse(order.begin(), order.end());
	for(auto [radius, idx, x]: order)
	{
		// cout << "order(" << radius << ", " << idx << ", " << x << ")" << endl;
		// cout << "Query(" << x << ") = " << Query(root, x) << endl;
		if(Query(root, x) != idx)
		{
			continue;
		}
		// cout << "Update(" << x - radius << ", " << x + radius << ") with " << idx << endl;
		Update(root, x - radius, x + radius, idx);
	}
	for(int i = 1; i <= n; i++)
	{
		cout << Query(root, circle[i][0]) << " ";
	}
	cout << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

/*
Sample 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

*/

Compilation message (stderr)

circle_selection.cpp: In function 'void Solve()':
circle_selection.cpp:108:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |  for(auto [radius, idx, x]: order)
      |           ^
circle_selection.cpp:113:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |  for(auto [radius, idx, x]: order)
      |           ^

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