Submission #1225481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225481		jerzyk	Mixture (BOI20_mixture)	C++20	100 / 100	132 ms	9268 KiB

Mixture

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100 * 1000 + 7;
const ld I = (ld)1000000 * (ld)1000000 * (ld)1000000;
ll il1, il2;
pair<int, ld> pkt[N];
map<ld, int> dody, ujy;

pair<int, ld> Change(ll a, ll b, ll c, ll ap, ll bp, ll cp)
{
	pair<int, ld> w;
	ld x, y;
	ll gcd;
	gcd = __gcd(ap, __gcd(bp, cp));
	ap /= gcd;
	bp /= gcd;
	cp /= gcd;
	gcd = __gcd(a, __gcd(b, c));
	a /= gcd;
	b /= gcd;
	c /= gcd;
	x = (ld)(((a + b) * (ap + bp + cp) - (ap + bp) * (a + b + c)));
	y = (ld)(((a + c) * (ap + bp + cp) - (ap + cp) * (a + b + c)));
	w.first = 0;
	if(x != (ld)0 || y != (ld)0)
	{	
		if(y > (ld)0 || (y == (ld)0 && x > (ld)0))
			w.first = 1;
		else
			w.first = -1;
	}
	//cout << a << " " << b << " " << c << " " << ap << " " << bp << " " << cp << "\n";
	//cout << x << " " << y << "\n";
	if(y == (ld)0)
		w.second = I;
	else
		w.second = x / y;
	return w;
}

bool Czy3()
{
	ld d1, d2, u1, u2;
	bool w1, w2;
	if(dody.size() == 0 || ujy.size() == 0)
		return false;
	d1 = (*dody.begin()).first;
	d2 = (*dody.rbegin()).first;
	u1 = (*ujy.begin()).first;
	u2 = (*ujy.rbegin()).first;
	w1 = false;
	if(ujy.lower_bound(d1) != ujy.end())
		if((*ujy.lower_bound(d1)).first <= d2)
			w1 = true;
	w2 = false;
	if(dody.lower_bound(u1) != dody.end())
		if((*dody.lower_bound((u1))).first <= u2)
			w2 = true;
	if(w1 || w2)
		return true;
	return false;
}

void Dodaj(int ws, ld v)
{
	if(ws == 0)
	{
		++il1;
		return;
	}
	if(ws == 1)
	{
		if(ujy.find(v) != ujy.end())
			il2 += (ll)ujy[v];
		if(dody.find(v) == dody.end())
			dody[v] = 0;
		++dody[v];
	}else
	{
		if(dody.find(v) != dody.end())
			il2 += (ll)dody[v];
		if(ujy.find(v) == ujy.end())
			ujy[v] = 0;
		++ujy[v];
	}
}

void Usun(int ws, ld v)
{
	if(ws == 0)
	{
		--il1;
		return;
	}
	if(ws == 1)
	{
		if(ujy.find(v) != ujy.end())
			il2 -= (ll)ujy[v];
		--dody[v];
		if(dody[v] == 0)
			dody.erase(v);
	}else
	{
		if(dody.find(v) != dody.end())
			il2 -= (ll)dody[v];
		--ujy[v];
		if(ujy[v] == 0)
			ujy.erase(v);
	}
}

void Mixture()
{
	int n, l, v, w, i;
	ll a, b, c, a1, b1, c1;
	char x;
	l = 0;
	cin >> a1 >> b1 >> c1;
	cin >> n;
	il1 = 0LL;
	il2 = 0LL;
	for(i = 1; i <= n; ++i)
	{
		cin >> x;
		if(x == 'A')
		{
			cin >> a >> b >> c;
			++l;
			pkt[l] = Change(a, b, c, a1, b1, c1);
			//cout << l << " " << pkt[l].first << " " << pkt[l].second << "\n";
			Dodaj(pkt[l].first, pkt[l].second);
		}
		if(x == 'R')
		{
			cin >> v;
			Usun(pkt[v].first, pkt[v].second);
		}
		//cout << "il2: " << il2 << "\n";
		w = 0;
		if(Czy3())
			w = 3;
		if(il2 > 0)
			w = 2;
		if(il1 > 0)
			w = 1;
		cout << w << "\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Mixture();

	return 0;
}

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