oj.uz

답안 #149157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149157 2019-09-01T05:50:44 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 3000 ms 33064 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{
	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;
}

Compilation message

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.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 262 ms 23800 KB Output is correct
4 Correct 243 ms 23928 KB Output is correct
5 Correct 113 ms 11256 KB Output is correct
6 Correct 1957 ms 30952 KB Output is correct
7 Correct 2108 ms 30952 KB Output is correct
8 Correct 2082 ms 30952 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 16 ms 9984 KB Output is correct
3 Correct 627 ms 25908 KB Output is correct
4 Correct 595 ms 25940 KB Output is correct
5 Correct 71 ms 10704 KB Output is correct
6 Correct 2021 ms 30116 KB Output is correct
7 Correct 1759 ms 30116 KB Output is correct
8 Correct 1755 ms 30116 KB Output is correct

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 262 ms 23800 KB Output is correct
4 Correct 243 ms 23928 KB Output is correct
5 Correct 113 ms 11256 KB Output is correct
6 Correct 1957 ms 30952 KB Output is correct
7 Correct 2108 ms 30952 KB Output is correct
8 Correct 2082 ms 30952 KB Output is correct
9 Correct 11 ms 9728 KB Output is correct
10 Correct 16 ms 9984 KB Output is correct
11 Correct 627 ms 25908 KB Output is correct
12 Correct 595 ms 25940 KB Output is correct
13 Correct 71 ms 10704 KB Output is correct
14 Correct 2021 ms 30116 KB Output is correct
15 Correct 1759 ms 30116 KB Output is correct
16 Correct 1755 ms 30116 KB Output is correct
17 Correct 105 ms 12280 KB Output is correct
18 Correct 17 ms 9984 KB Output is correct
19 Correct 815 ms 26164 KB Output is correct
20 Correct 819 ms 26164 KB Output is correct
21 Correct 114 ms 11000 KB Output is correct
22 Execution timed out 3096 ms 33064 KB Time limit exceeded
23 Halted 0 ms 0 KB -