Submission #745089

#	Time	Username	Problem	Language	Result	Execution time	Memory
745089		b00norp	Circle selection (APIO18_circle_selection)	C++14	0 / 100	1826 ms	71460 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;

vector<int> seg(N * 4, INF);
int parl[N], parr[N];

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];
}

void Update(int l, int r, int pos, int ql, int qr, int qval)
{
	if(ql <= l && r <= qr)
	{
		seg[pos] = qval;
		return;
	}
	if(ql > r || l > qr)
	{
		return;
	}
	int mid = (l + r) / 2;
	Update(l, mid, pos * 2, ql, qr, qval);
	Update(mid + 1, r, pos * 2 + 1, ql, qr, qval);
}

int Query(int l, int r, int pos, int qpos)
{
	if(seg[pos] != INF)
	{
		return seg[pos];
	}
	int mid = (l + r) >> 1;
	if(qpos <= mid)
	{
		return Query(l, mid, pos * 2, qpos);
	}
	return Query(mid + 1, r, pos * 2 + 1, qpos);
}

int FindL(int x)
{
	if(x == parl[x])
	{
		return x;
	}
	return parl[x] = FindL(parl[x]);
}

void UniteL(int u, int v)
{
	u = FindL(u);
	v = FindL(v);
	if(u == v) return;
	parl[max(u, v)] = min(u, v);
}

int FindR(int x)
{
	if(x == parr[x])
	{
		return x;
	}
	return parr[x] = FindR(parr[x]);
}

void UniteR(int u, int v)
{
	u = FindR(u);
	v = FindR(v);
	if(u == v) return;
	parr[min(u, v)] = max(u, v);
}

void Solve() 
{
	int n;
	cin >> n;
	vector<array<int, 3> > circle(n + 1);
	map<int, int> mp, revmp;
	for(int i = 1; i <= n; i++)
	{
		parl[i] = i;
		parr[i] = i;
		cin >> circle[i][0] >> circle[i][1] >> circle[i][2];
		mp[circle[i][0]]++;
	}
	int cnt = 0;
	for(auto i: mp)
	{
		mp[i.first] = ++cnt;
		revmp[cnt] = i.first;
	}
	for(int i = 1; i <= n; i++)
	{
		circle[i][0] = mp[circle[i][0]];
	}
	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(1, n, 1, x, x, idx);
	}
	// cout << "cnt = " << cnt << endl;
	// for(int i = 1; i <= cnt; i++)
	// {
	// 	cout << revmp[i] << " ";
	// }
	// cout << endl;
	reverse(order.begin(), order.end());
	for(auto [radius, idx, x]: order)
	{
		// cout << "order(" << radius << ", " << idx << ", " << x << ")" << endl;
		// cout << "Query(" << x << ") = " << Query(1, n, 1, x) << endl;
		if(Query(1, n, 1, x) != idx)
		{
			continue;
		}
		int left = x, right = x;
		int l = 1, r = x;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(revmp[mid] >= revmp[x] - radius)
			{
				r = mid - 1;
				left = mid;
			}
			else
			{
				l = mid + 1;
			}
		}
		l = x;
		r = cnt;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(revmp[mid] <= revmp[x] + radius)
			{
				l = mid + 1;
				right = mid;
			}
			else
			{
				r = mid - 1;
			}
		}
		left = FindR(left);
		right = FindL(right);
		// cout << "left = " << left << ", right = " << right << endl;
		Update(1, n, 1, left, right, idx);
		for(int i = left; i <= right; i++)
		{
			UniteL(i, i - 1);
			UniteR(i, i + 1);
		}
	}
	for(int i = 1; i <= n; i++)
	{
		cout << Query(1, n, 1, 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:115:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |  for(auto [radius, idx, x]: order)
      |           ^
circle_selection.cpp:126:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |  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