Submission #829922

#	Time	Username	Problem	Language	Result	Execution time	Memory
829922		caganyanmaz	Circle selection (APIO18_circle_selection)	C++14	12 / 100	1785 ms	371880 KiB

circle_selection

#include <bits/stdc++.h>

#define pb push_back
using namespace std;
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif

constexpr static int RE = 1e9 + 1;
constexpr static int LE = -1e9 + 1;
constexpr static int INF = 1e6;
constexpr static int MXN = 3e5;
struct SegTree
{
	vector<int> data, lazy, left, right;
	SegTree() : data(1, INF), lazy(1, INF), left(1, -1), right(1, -1) {}
	void push(int l, int r, int index)
	{
		if (r - l == 1)
			return;
		if (left[index] != -1)
			return;
		left[index] = data.size();
		left.pb(-1), right.pb(-1), data.pb(INF), lazy.pb(INF);
		right[index] = data.size();
		left.pb(-1), right.pb(-1), data.pb(INF), lazy.pb(INF);
	}
	void push_lazy(int l, int r, int index)
	{
		data[index] = min(data[index], lazy[index]);
		if (r - l > 1)
		{
			lazy[left[index]] = min(lazy[left[index]], lazy[index]);
			lazy[right[index]] = min(lazy[right[index]], lazy[index]);
		}
		lazy[index] = INF;
	}
	void set(int l, int r, int index, int ss, int ee, int val)
	{
		push(l, r, index);
		push_lazy(l, r, index);
		if (l >= ee || ss >= r)
			return;
		if (ee >= r && l >= ss)
		{
			lazy[index] = val;
			push_lazy(l, r, index);
			return;
		}
		int m = l+r>>1;
		set(l, m, left[index], ss, ee, val);
		set(m, r, right[index], ss, ee, val);
		data[index] = min(data[left[index]], data[right[index]]);
	}
	int get(int l, int r, int index, int ss, int ee)
	{
		push(l, r, index);
		push_lazy(l, r, index);
		if (l >= ee || ss >= r)
			return INF;
		if (ee >= r && l >= ss)
			return data[index];
		int m = l+r>>1;
		int lres = get(l, m, left[index], ss, ee);
		int rres = get(m, r, right[index], ss, ee);
		return min(lres, rres);
	}
	void set(int ss, int ee, int val) { set(LE, RE, 0, ss, ee, val); }
	int get(int ss, int ee) { return get(LE, RE, 0, ss, ee); }
};


array<int, 3> p[MXN]; // Radius size, index, position
int res[MXN];
int main()
{
	SegTree st;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x, y, r;
		cin >> x >> y >> r;
		assert(y == 0);
		p[i] = {-r, i, x};
	}
	sort(p, p+n);
	int a = st.get(11, 12);
	debug(a);
	debug(st.get(10, 20));
	for (int j = 0; j < n; j++)
	{
		auto [r, i, x] = p[j];
		r *= -1;
		int val = st.get(x-r-1, x+r+1);
		if (val != INF)
		{
			res[i] = p[val][1];
			continue;
		}
		st.set(x-r, x+r, j);
		res[i] = i;
	}
	debug(st.get(100, 101));
	for (int i = 0; i < n; i++)
		cout << (res[i]+1) << " ";
	cout << "\n";
}

Compilation message (stderr)

circle_selection.cpp: In member function 'void SegTree::set(int, int, int, int, int, int)':
circle_selection.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int m = l+r>>1;
      |           ~^~
circle_selection.cpp: In member function 'int SegTree::get(int, int, int, int, int)':
circle_selection.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int m = l+r>>1;
      |           ~^~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:95:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |   auto [r, i, x] = p[j];
      |        ^
circle_selection.cpp:90:6: warning: unused variable 'a' [-Wunused-variable]
   90 |  int a = st.get(11, 12);
      |      ^

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