Submission #810284

#	Time	Username	Problem	Language	Result	Execution time	Memory
810284		ymm	Mixture (BOI20_mixture)	C++17	100 / 100	536 ms	68240 KiB

Mixture

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;

#define double long double
typedef complex<double> pnt;

const double eps = 1e-11;

struct obj {
	pnt P;
	bool first;
	pnt F;
	double argF;
	double mn, mx;
	multiset<double> S;
	bool line;
	bool zero;

	double add(pnt A, double argA)
	{
		if (!first) {
			F = A;
			argF = argA;
			first = 1;
		}
		double theta = argA - argF;
		if (theta > M_PI)
			theta -= 2*M_PI;
		if (theta < -M_PI)
			theta += 2*M_PI;
		S.insert(theta);
		if (abs(A.real()) < eps && abs(A.imag()) < eps) {
			zero = 1;
			return theta;
		}
		mn = min(mn, theta);
		mx = max(mx, theta);
		double theta2 = theta;
		if (theta > 0)
			theta2 -= M_PI;
		else
			theta2 += M_PI;
		auto it = S.lower_bound(theta2-eps);
		if (it != S.end() && *it - theta2 < eps)
			line = 1;
		return theta;
	}

	int get_ans() {
		if (zero)
			return 1;
		if (line)
			return 2;
		if (first && mx - mn > M_PI - eps)
			return 3;
		return 0;
	}
};

struct preprocP {
	pnt P;
	double a;
};

pnt normalize(double x, double y, double z)
{
	double sum = x+y+z;
	x /= sum;
	y /= sum;
	return {x, y};
}

pnt P;
const int N = 100'010;
int n;

namespace seg {
	vector<preprocP> t[N*4];
	void add(int l, int r, const preprocP &P, int i, int b, int e) {
		if (l <= b && e <= r) {
			t[i].push_back(P);
			return;
		}
		if (r <= b || e <= l)
			return;
		add(l, r, P, 2*i+1, b, (b+e)/2);
		add(l, r, P, 2*i+2, (b+e)/2, e);
	}
	void add(int l, int r, pnt P) {
		preprocP Q;
		Q.P = P-::P;
		Q.a = arg(Q.P);
		add(l, r, Q, 0, 0, n);
	}

	void dfs(obj &o0, int i, int b, int e) {
		multiset<double> marg;
		o0.S.swap(marg);
		obj o = o0;
		o.S.swap(marg);
		vector<double> kooft;
		for (auto P : t[i])
			kooft.push_back(o.add(P.P, P.a));
		if (e-b == 1) {
			cout << o.get_ans() << '\n';
		} else {
			dfs(o, 2*i+1, b, (b+e)/2);
			dfs(o, 2*i+2, (b+e)/2, e);
		}
		o.S.swap(marg);
		for (auto x : kooft)
			marg.erase(marg.find(x));
		o0.S.swap(marg);
	}
	void dfs(pnt P) {
		obj o = {};
		o.P = P;
		dfs(o, 0, 0, n);
	}
}

pnt readp()
{
	ll x, y, z;
	cin >> x >> y >> z;
	return normalize(x, y, z);
}

pnt a[N];
int l[N];
bool rem[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	P = readp();
	cin >> n;
	int cnt = 0;
	Loop (i,0,n) {
		char c;
		cin >> c;
		if (c == 'A') {
			a[cnt] = readp();
			l[cnt] = i;
			++cnt;
		} else {
			int x;
			cin >> x;
			--x;
			seg::add(l[x], i, a[x]);
			rem[x] = 1;
		}
	}
	Loop (i,0,cnt) {
		if (!rem[i])
			seg::add(l[i], n, a[i]);
	}
	seg::dfs(P);
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40