oj.uz

Submission #149162

# Submission time Handle Problem Language Result Execution time Memory
149162 2019-09-01T05:51:57 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1870 ms 33188 KB 
#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;
}

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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 199 ms 23800 KB Output is correct
4 Correct 194 ms 23928 KB Output is correct
5 Correct 51 ms 11256 KB Output is correct
6 Correct 820 ms 30696 KB Output is correct
7 Correct 923 ms 30952 KB Output is correct
8 Correct 801 ms 30996 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9728 KB Output is correct
2 Correct 14 ms 9728 KB Output is correct
3 Correct 521 ms 25908 KB Output is correct
4 Correct 503 ms 26168 KB Output is correct
5 Correct 45 ms 10744 KB Output is correct
6 Correct 1093 ms 29988 KB Output is correct
7 Correct 1064 ms 30116 KB Output is correct
8 Correct 1139 ms 30116 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 199 ms 23800 KB Output is correct
4 Correct 194 ms 23928 KB Output is correct
5 Correct 51 ms 11256 KB Output is correct
6 Correct 820 ms 30696 KB Output is correct
7 Correct 923 ms 30952 KB Output is correct
8 Correct 801 ms 30996 KB Output is correct
9 Correct 11 ms 9728 KB Output is correct
10 Correct 14 ms 9728 KB Output is correct
11 Correct 521 ms 25908 KB Output is correct
12 Correct 503 ms 26168 KB Output is correct
13 Correct 45 ms 10744 KB Output is correct
14 Correct 1093 ms 29988 KB Output is correct
15 Correct 1064 ms 30116 KB Output is correct
16 Correct 1139 ms 30116 KB Output is correct
17 Correct 103 ms 12284 KB Output is correct
18 Correct 17 ms 9984 KB Output is correct
19 Correct 638 ms 26168 KB Output is correct
20 Correct 634 ms 26164 KB Output is correct
21 Correct 69 ms 11000 KB Output is correct
22 Correct 1870 ms 33188 KB Output is correct
23 Correct 1841 ms 33188 KB Output is correct
24 Correct 1771 ms 33188 KB Output is correct