oj.uz

Submission #745064

# Submission time Handle Problem Language Result Execution time Memory
745064 2023-05-19T11:08:39 Z b00norp Circle selection (APIO18_circle_selection) C++14
0 / 100
 767 ms 1048576 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Runtime error 635 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 740 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 646 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 767 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Runtime error 635 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Runtime error 635 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -