제출 #149162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149162		CHT를 사랑하는 모임 (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	100 / 100	1870 ms	33188 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const int N=3e5+5;
const ll mod=1e9+7;
int n;
ll a[N],d[N],p[N];
struct Lichao{
	int cn=1;
	vector<pii> tree;
	vector<int> le,re;
	pll func[N];
	void ins(int nd,db L,db R,int x)
	{
		if(!tree[nd].fi){
			tree[nd].fi=x;
			return;
		}
		db M=(L+R)/2.;
		if(!tree[nd].se){
			db r1=(db)func[tree[nd].fi].fi*M+(db)func[tree[nd].fi].se;
			db r2=(db)func[x].fi*M+(db)func[x].se;
			tree[nd].se=x;
			if(r1<r2) swap(tree[nd].fi,tree[nd].se);
			return;
		}
		db m1=(db)func[tree[nd].fi].fi*M+(db)func[tree[nd].fi].se;
		db m2=(db)func[tree[nd].se].fi*M+(db)func[tree[nd].se].se;
		db m3=(db)func[x].fi*M+(db)func[x].se;
		db l1=(db)func[tree[nd].fi].fi*L+(db)func[tree[nd].fi].se;
		db l2=(db)func[tree[nd].se].fi*L+(db)func[tree[nd].se].se;
		db l3=(db)func[x].fi*L+(db)func[x].se;
		db r1=(db)func[tree[nd].fi].fi*R+(db)func[tree[nd].fi].se;
		db r2=(db)func[tree[nd].se].fi*R+(db)func[tree[nd].se].se;
		db r3=(db)func[x].fi*R+(db)func[x].se;
		if(m3>m1){
			swap(tree[nd].fi,tree[nd].se);
			swap(tree[nd].fi,x);
			if(min(l1,l3)>=l2&&min(r1,r3)>=r2) return;
			if(l2>=min(l1,l3)){
				if(!le[nd]){
					le[nd]=++cn;
					tree.push_back(pii(0,0));
					le.push_back(0); re.push_back(0);
				}
				ins(le[nd],L,M,x);
			}
			//if(r2>=min(r1,r3)){
			else{
				if(!re[nd]){
					re[nd]=++cn;
					tree.push_back(pii(0,0));
					le.push_back(0); re.push_back(0);
				}
				ins(re[nd],M,R,x);
			}
		}
		else if(m3>m2){
			swap(tree[nd].se,x);
			if(min(l1,l3)>=l2&&min(r1,r3)>=r2) return;
			if(l2>=min(l1,l3)){
				if(!le[nd]){
					le[nd]=++cn;
					tree.push_back(pii(0,0));
					le.push_back(0); re.push_back(0);
				}
				ins(le[nd],L,M,x);
			}
			//if(r2>=min(r1,r3)){
			else{
				if(!re[nd]){
					re[nd]=++cn;
					tree.push_back(pii(0,0));
					le.push_back(0); re.push_back(0);
				}
				ins(re[nd],M,R,x);
			}
		}
		else{
			if(min(l1,l2)>=l3&&min(r1,r2)>=r3) return;
			if(l3>=min(l1,l2)){
				if(!le[nd]){
					le[nd]=++cn;
					tree.push_back(pii(0,0));
					le.push_back(0); re.push_back(0);
				}
				ins(le[nd],L,M,x);
			}
			//if(r3>=min(r1,r2)){
			else{
				if(!re[nd]){
					re[nd]=++cn;
					tree.push_back(pii(0,0));
					le.push_back(0); re.push_back(0);
				}
				ins(re[nd],M,R,x);
			}
		}
	}
	void init(){
		tree.push_back(pii(0,0)); le.push_back(0); re.push_back(0);
		tree.push_back(pii(0,0)); le.push_back(0); re.push_back(0);
		for(int i=1;i<=n;i++) ins(1,0,1e9,i);
	}
	pair<pll,pll> query(int nd,db L,db R,db x,ll rx,ll ry)
	{
		pll r1=pll(-1e9,-1e9),r2=pll(-1e9,-1e9);
		if(!nd) return {r1,r2};
		if(tree[nd].fi){
			ll f1=rx*func[tree[nd].fi].fi+ry*func[tree[nd].fi].se;
			r1=pll(f1,tree[nd].fi);
		}
		if(tree[nd].se){
			ll f2=rx*func[tree[nd].se].fi+ry*func[tree[nd].se].se;
			r2=pll(f2,tree[nd].se);
		}
		if(r1<r2) swap(r1,r2);
		db M=(L+R)/2.;
		pair<pll,pll> it;
		pll n1,n2;
		if(x<=M) it=query(le[nd],L,M,x,rx,ry);
		else it=query(re[nd],M,R,x,rx,ry);
		n1=it.fi;
		n2=it.se;
		if(n1>r1){
			swap(r1,r2);
			swap(r1,n1);
		}
		else if(n1>r2) swap(r2,n1);
		if(n2>r1){
			swap(r1,r2);
			swap(r1,n2);
		}
		else if(n2>r2) swap(r2,n2);
		return {r1,r2};
	}
	pair<pll,pll> query(db x,ll rx,ll ry){
		return query(1,0,1e9,x,rx,ry);
	}
}t1,t2;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n=A.size();
	for(int i=1;i<=n;i++){
		a[i]=A[i-1];
		d[i]=D[i-1];
		p[i]=P[i-1];
		t1.func[i]=pll(a[i],p[i]);
		t2.func[i]=pll(d[i],p[i]);
	}
	t1.init(); t2.init();
}

long long BestSquad(int X, int Y){
	ll V=__gcd(X,Y);
	auto p1=t1.query((db)X/(db)Y,X,Y),p2=t2.query((db)X/(db)Y,X,Y);
	if(p1.fi.se==p2.fi.se) return max(p1.fi.fi+p2.se.fi,p1.se.fi+p2.fi.fi);
	return p1.fi.fi+p2.fi.fi;
}

컴파일 시 표준 에러 (stderr) 메시지

squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:163:5: warning: unused variable 'V' [-Wunused-variable]
  ll V=__gcd(X,Y);
     ^

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53