oj.uz

답안 #745089

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
745089 2023-05-19T11:38:19 Z b00norp 원 고르기 (APIO18_circle_selection) C++14
0 / 100
 1826 ms 71460 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;

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 650 ms 71460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1826 ms 71416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -