Submission #103866

#	Time	Username	Problem	Language	Result	Execution time	Memory
103866		dupreez	Circle selection (APIO18_circle_selection)	C++14	12 / 100	2149 ms	50280 KiB

circle_selection

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <cstdio>
#include <cmath>
#include <bitset>
#define mk make_pair
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pos;

const ll MOD = 1000000007, N =300010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -7230040172838, MAX = 7230040172838;
const int S = 60;
ll mn(ll a, ll b) {
	if (a == -1)return b;
	if (b == -1)return a;
	return min(a, b);
}
static ll gcd(ll v1, ll v2) {
	if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
}

ll pw(ll v1, ll v2) {
	ll v3 = 1;
	while (v2 > 0) {
		if (v2 % 2)v3 = (v3*v1) % MOD;
		v1 = (v1*v1) % MOD;
		v2 /= 2;
	}
	return v3;
}

int n, as[N], xv[N], rgl[N*2];
pos x[N], r[N];
set<pos> rg;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int v1;
		cin >> xv[i] >> v1 >> r[i].first;
		r[i].second = -i;
		rg.insert(mk(xv[i] - r[i].first, i));
		rg.insert(mk(xv[i] + r[i].first, i));
		if (v1 != 0)return 0;
	}

	sort(r + 1, r + n + 1);
	memset(as, -1, sizeof(as));
	for (int i = n; i >= 1; i--) {
		int ci = -r[i].second;
		if (as[ci] != -1)continue;
		int lb = xv[ci] - r[i].first, ub = xv[ci] + r[i].first;
		for (auto i1 = rg.lower_bound(mk(lb,-1)); i1!=rg.end()&&(*i1).first <= ub; i1 = rg.lower_bound(mk(lb, -1))) {
			int ni = (*i1).second;
			if (as[ni] == -1)as[ni] = ci;
			rg.erase(i1);
		}
	}
	for (int i = 1; i <= n; i++)cout << as[i] << endl;
	return 0;
}

Compilation message (stderr)

circle_selection.cpp: In function 'll gcd(ll, ll)':
circle_selection.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
  ^~
circle_selection.cpp:27:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);
                         ^~

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