Submission #1326427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326427		boclobanchat	Mixture (BOI20_mixture)	C++20	100 / 100	445 ms	59008 KiB

Mixture

#include<bits/stdc++.h>
using namespace std;
const __int128 base=183667183667;
struct ftype
{
	__int128 a,b;
	ftype& operator+= (const ftype& p)
	{
		a=a*p.b+b*p.a,b*=p.b;
		return *this;
	}
	ftype& operator-= (const ftype& p)
	{
		a=a*p.b-b*p.a,b*=p.b;
		return *this;
	}
	ftype& operator*= (const ftype& p)
	{
		a*=p.a,b*=p.b;
		return *this;
	}
};
ftype operator+ (const ftype& x,const ftype& y)
{
	return (ftype){x.a*y.b+x.b*y.a,x.b*y.b};
}
ftype operator- (const ftype& x,const ftype& y)
{
	return (ftype){x.a*y.b-x.b*y.a,x.b*y.b};
}
ftype operator* (const ftype& x,const ftype& y)
{
	return (ftype){x.a*y.a,x.b*y.b};
}
ftype operator/ (const ftype& x,const ftype& y)
{
	return (ftype){x.a*y.b,x.b*y.a};
}
struct point
{
	ftype x,y;
	point& operator+= (const point& a)
	{
		x+=a.x,y+=a.y;
		return *this;
	}
	point& operator-= (const point& a)
	{
		x-=a.x,y-=a.y;
		return *this;
	}
	point& operator*= (ftype a)
	{
		x*=a,y*=a;
		return *this;
	}
};
point operator+ (const point& a,const point& b)
{
	return (point){a.x+b.x,a.y+b.y};
}
point operator- (const point& a,const point& b)
{
	return (point){a.x-b.x,a.y-b.y};
}
ftype dot(point a,point b)
{
	return a.x*b.x+a.y*b.y;
}
ftype cross(point a,point b)
{
	return a.x*b.y-a.y*b.x;
}
bool crossz(point a,point b)
{
	ftype x=a.x*b.y,y=a.y*b.x;
	__int128 xa=(x.a/base)*(y.b/base),xb=(x.a%base)*(y.b%base)+(x.a/base)*(y.b%base)*base+(x.a%base)*(y.b/base)*base;
	xa+=xb/base/base,xb%=base*base;
	__int128 ya=(y.a/base)*(x.b/base),yb=(y.a%base)*(x.b%base)+(y.a/base)*(x.b%base)*base+(y.a%base)*(x.b/base)*base;
	ya+=yb/base/base,yb%=base*base;
	return (xa>ya||(xa==ya&&xb>yb));
}
bool crosszz(point a,point b)
{
	ftype x=a.x*b.y,y=a.y*b.x;
	__int128 xa=(x.a/base)*(y.b/base),xb=(x.a%base)*(y.b%base)+(x.a/base)*(y.b%base)*base+(x.a%base)*(y.b/base)*base;
	xa+=xb/base/base,xb%=base*base;
	__int128 ya=(y.a/base)*(x.b/base),yb=(y.a%base)*(x.b%base)+(y.a/base)*(x.b%base)*base+(y.a%base)*(x.b/base)*base;
	ya+=yb/base/base,yb%=base*base;
	return (xa==ya&&xb==yb);
}
bool crossl(point a,point b)
{
	ftype x=a.x*b.y,y=a.y*b.x;
	__int128 xa=(x.a/base)*(y.b/base),xb=(x.a%base)*(y.b%base)+(x.a/base)*(y.b%base)*base+(x.a%base)*(y.b/base)*base;
	xa+=xb/base/base,xb%=base*base;
	__int128 ya=(y.a/base)*(x.b/base),yb=(y.a%base)*(x.b%base)+(y.a/base)*(x.b%base)*base+(y.a%base)*(x.b/base)*base;
	ya+=yb/base/base,yb%=base*base;
	return (xa<ya||(xa==ya&&xb<yb));
}
bool up(point a)
{
	if(a.y.a>0) return true;
	if(a.y.a==0&&a.x.a>0) return true;
	return false;
}
bool comp(pair<point,int> x,pair<point,int> y)
{
	point a=x.first,b=y.first;
	if(up(a)==up(b))
	{
		if(crosszz(a,b)) return x.second<y.second;
		return crossz(a,b);
	}
	return up(a)<up(b);
}
ftype ab(ftype res)
{
	__int128 g=__gcd(res.a,res.b);
	if(res.b/g<0) return {-res.a/g,-res.b/g};
	return {res.a/g,res.b/g};
}
point compress(int x,int y,int z)
{
	return {{x,x+y+z},{y,x+y+z}};
}
const int MAXN=2e5+5;
pair<point,int> val[MAXN];
point A[MAXN],B[MAXN];
int Q[MAXN],pos[MAXN];
set<int> st;
vector<__int128> vi[MAXN];
map< vector<__int128>,int > mp;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x,y,z,q;
    cin>>x>>y>>z>>q;
    point a=compress(x,y,z);
    int cnt=0;
    for(int i=1;i<=q;i++)
    {
    	char c;
    	cin>>c;
    	if(c=='A')
    	{
    		int x,y,z;
    		cin>>x>>y>>z;
    		Q[i]=++cnt,val[cnt]={A[cnt]=compress(x,y,z)-a,cnt};
    		if(A[cnt].y.a==0) vi[cnt]={1,1,0,up(A[cnt])};
    		else vi[cnt]={ab(A[cnt].x/A[cnt].y).a,ab(A[cnt].x/A[cnt].y).b,1,up(A[cnt])};
		}
		else
		{
			int res;
			cin>>res;
			Q[i]=-res;
		}
	}
	sort(val+1,val+cnt+1,comp);
	for(int i=1;i<=cnt;i++) B[i]=val[i].first,pos[val[i].second]=i;
	int cnz=0,cc=0,crs=0,diff=0;
	long long cp=0;
	for(int i=1;i<=q;i++)
	{
		int p=abs(Q[i]);
		if(Q[i]>0)
		{
			cc++,cnz+=(A[p].x.a==0&&A[p].y.a==0);
			diff+=(mp[vi[p]]++==0),vi[p].back()^=1,cp+=mp[vi[p]],vi[p].back()^=1;
			st.insert(pos[p]);
			auto res=st.find(pos[p]);
			if(cc==2)
			{
				if(res==st.begin()) crs=(crossl(B[*res],B[*next(res)]))+(crossl(B[*next(res)],B[*res]));
				else crs=(crossl(B[*res],B[*prev(res)]))+(crossl(B[*prev(res)],B[*res]));
			}
			else if(cc>2)
			{
				int pl,pr;
				if(res==st.begin()) pl=*prev(st.end());
				else pl=*prev(res);
				if(res==prev(st.end())) pr=*st.begin();
				else pr=*next(res);
				crs-=(crossl(B[pl],B[pr]))-(crossl(B[pl],B[*res]))-(crossl(B[*res],B[pr]));
			}
		}
		else
		{
			cc--,cnz-=(A[p].x.a==0&&A[p].y.a==0);
			vi[p].back()^=1,cp-=mp[vi[p]],vi[p].back()^=1,diff-=(--mp[vi[p]]==0);
			auto res=st.find(pos[p]);
			if(cc==1) crs=0;
			else
			{
				int pl,pr;
				if(res==st.begin()) pl=*prev(st.end());
				else pl=*prev(res);
				if(res==prev(st.end())) pr=*st.begin();
				else pr=*next(res);
				crs+=(crossl(B[pl],B[pr]))-(crossl(B[pl],B[*res]))-(crossl(B[*res],B[pr]));
			}
			st.erase(pos[p]);
		}
		if(cnz) cout<<"1\n";
		else if(cp) cout<<"2\n";
		else if(diff-(cnz>0)>=3&&!crs) cout<<"3\n";
		else cout<<"0\n";
	}
}

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