Submission #810277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810277	2023-08-06T07:53:55 Z	ymm	Mixture (BOI20_mixture)	C++17	60 / 100	61 ms	15380 KB

Mixture

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

typedef complex<double> pnt;

const double eps = 1e-6;

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9684 KB	Output is correct
7	Correct	4 ms	9696 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	4 ms	9684 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9712 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	4 ms	9684 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9684 KB	Output is correct
7	Correct	4 ms	9696 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	4 ms	9684 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9712 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	4 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	4 ms	9632 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9812 KB	Output is correct
24	Correct	5 ms	9804 KB	Output is correct
25	Correct	5 ms	9816 KB	Output is correct
26	Correct	5 ms	9812 KB	Output is correct
27	Correct	5 ms	9684 KB	Output is correct
28	Correct	5 ms	9812 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	7 ms	9812 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	5 ms	9812 KB	Output is correct
33	Correct	5 ms	9684 KB	Output is correct
34	Correct	5 ms	9828 KB	Output is correct
35	Correct	5 ms	9684 KB	Output is correct
36	Correct	7 ms	9684 KB	Output is correct

Subtask #3
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9684 KB	Output is correct
7	Correct	4 ms	9696 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	4 ms	9684 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9712 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	4 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	4 ms	9632 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9812 KB	Output is correct
24	Correct	5 ms	9804 KB	Output is correct
25	Correct	5 ms	9816 KB	Output is correct
26	Correct	5 ms	9812 KB	Output is correct
27	Correct	5 ms	9684 KB	Output is correct
28	Correct	5 ms	9812 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	7 ms	9812 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	5 ms	9812 KB	Output is correct
33	Correct	5 ms	9684 KB	Output is correct
34	Correct	5 ms	9828 KB	Output is correct
35	Correct	5 ms	9684 KB	Output is correct
36	Correct	7 ms	9684 KB	Output is correct
37	Correct	6 ms	9812 KB	Output is correct
38	Correct	5 ms	9812 KB	Output is correct
39	Correct	6 ms	9812 KB	Output is correct
40	Correct	6 ms	9812 KB	Output is correct
41	Correct	6 ms	9812 KB	Output is correct
42	Correct	6 ms	9788 KB	Output is correct
43	Correct	6 ms	9812 KB	Output is correct
44	Correct	6 ms	9812 KB	Output is correct
45	Correct	6 ms	9812 KB	Output is correct
46	Correct	11 ms	10452 KB	Output is correct
47	Correct	11 ms	10480 KB	Output is correct
48	Correct	13 ms	9776 KB	Output is correct
49	Correct	8 ms	9996 KB	Output is correct
50	Correct	8 ms	10068 KB	Output is correct
51	Correct	13 ms	10660 KB	Output is correct
52	Correct	15 ms	10876 KB	Output is correct
53	Correct	14 ms	10964 KB	Output is correct
54	Correct	15 ms	11068 KB	Output is correct
55	Correct	11 ms	10588 KB	Output is correct
56	Correct	11 ms	10632 KB	Output is correct

Subtask #4
0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	9684 KB	Output is correct
2	Correct	5 ms	9684 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	5 ms	9684 KB	Output is correct
5	Correct	5 ms	9684 KB	Output is correct
6	Correct	4 ms	9684 KB	Output is correct
7	Correct	4 ms	9696 KB	Output is correct
8	Correct	4 ms	9684 KB	Output is correct
9	Correct	4 ms	9684 KB	Output is correct
10	Correct	5 ms	9684 KB	Output is correct
11	Correct	5 ms	9684 KB	Output is correct
12	Correct	5 ms	9684 KB	Output is correct
13	Correct	4 ms	9684 KB	Output is correct
14	Correct	6 ms	9684 KB	Output is correct
15	Correct	4 ms	9684 KB	Output is correct
16	Correct	5 ms	9684 KB	Output is correct
17	Correct	5 ms	9712 KB	Output is correct
18	Correct	4 ms	9684 KB	Output is correct
19	Correct	4 ms	9684 KB	Output is correct
20	Correct	5 ms	9684 KB	Output is correct
21	Correct	4 ms	9632 KB	Output is correct
22	Correct	5 ms	9684 KB	Output is correct
23	Correct	5 ms	9812 KB	Output is correct
24	Correct	5 ms	9804 KB	Output is correct
25	Correct	5 ms	9816 KB	Output is correct
26	Correct	5 ms	9812 KB	Output is correct
27	Correct	5 ms	9684 KB	Output is correct
28	Correct	5 ms	9812 KB	Output is correct
29	Correct	5 ms	9684 KB	Output is correct
30	Correct	7 ms	9812 KB	Output is correct
31	Correct	5 ms	9684 KB	Output is correct
32	Correct	5 ms	9812 KB	Output is correct
33	Correct	5 ms	9684 KB	Output is correct
34	Correct	5 ms	9828 KB	Output is correct
35	Correct	5 ms	9684 KB	Output is correct
36	Correct	7 ms	9684 KB	Output is correct
37	Correct	6 ms	9812 KB	Output is correct
38	Correct	5 ms	9812 KB	Output is correct
39	Correct	6 ms	9812 KB	Output is correct
40	Correct	6 ms	9812 KB	Output is correct
41	Correct	6 ms	9812 KB	Output is correct
42	Correct	6 ms	9788 KB	Output is correct
43	Correct	6 ms	9812 KB	Output is correct
44	Correct	6 ms	9812 KB	Output is correct
45	Correct	6 ms	9812 KB	Output is correct
46	Correct	11 ms	10452 KB	Output is correct
47	Correct	11 ms	10480 KB	Output is correct
48	Correct	13 ms	9776 KB	Output is correct
49	Correct	8 ms	9996 KB	Output is correct
50	Correct	8 ms	10068 KB	Output is correct
51	Correct	13 ms	10660 KB	Output is correct
52	Correct	15 ms	10876 KB	Output is correct
53	Correct	14 ms	10964 KB	Output is correct
54	Correct	15 ms	11068 KB	Output is correct
55	Correct	11 ms	10588 KB	Output is correct
56	Correct	11 ms	10632 KB	Output is correct
57	Correct	16 ms	10964 KB	Output is correct
58	Correct	18 ms	10972 KB	Output is correct
59	Correct	16 ms	10992 KB	Output is correct
60	Correct	19 ms	10964 KB	Output is correct
61	Incorrect	61 ms	15380 KB	Output isn't correct
62	Halted	0 ms	0 KB	-

Submission #810277

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 30.0 / 30.0

Subtask #4 0 / 40.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
30.0 / 30.0

Subtask #4
0 / 40.0