oj.uz

답안 #149010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149010 2019-09-01T05:33:30 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) 최적의 팀 구성 (FXCUP4_squad) C++17
0 / 100
 1045 ms 35508 KB 
#include "squad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long 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{
	pii tree[2*N]; int cn=1,le[2*N]={0},re[2*N]={0};
	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;
				ins(le[nd],L,M,x);
			}
			if(r2>=min(r1,r3)){
				if(re[nd]) re[nd]=++cn;
				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;
				ins(le[nd],L,M,x);
			}
			if(r2>=min(r1,r3)){
				if(re[nd]) re[nd]=++cn;
				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;
				ins(le[nd],L,M,x);
			}
			if(r3>=min(r1,r2)){
				if(re[nd]) re[nd]=++cn;
				ins(re[nd],M,R,x);
			}
		}
	}
	void init(){
		for(int i=0;i<2*N;i++) tree[i]=pii(0,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);
		}
		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;
		vector<pll> v={r1,r2,n1,n2};
		sort(v.begin(),v.end());
		return {v[3],v[2]};
	}
	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;
}

Compilation message

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

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9856 KB Output is correct
2 Correct 13 ms 9856 KB Output is correct
3 Correct 277 ms 33276 KB Output is correct
4 Correct 250 ms 33272 KB Output is correct
5 Incorrect 115 ms 11384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 9856 KB Output is correct
2 Correct 27 ms 10104 KB Output is correct
3 Correct 1045 ms 35508 KB Output is correct
4 Correct 1006 ms 35508 KB Output is correct
5 Incorrect 85 ms 10984 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9856 KB Output is correct
2 Correct 13 ms 9856 KB Output is correct
3 Correct 277 ms 33276 KB Output is correct
4 Correct 250 ms 33272 KB Output is correct
5 Incorrect 115 ms 11384 KB Output isn't correct
6 Halted 0 ms 0 KB -