oj.uz

Submission #149095

# Submission time Handle Problem Language Result Execution time Memory
149095 2019-09-01T05:44:10 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 31140 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)){
				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)){
				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)){
				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);
		}
		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:151: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 10 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 291 ms 23800 KB Output is correct
4 Correct 256 ms 23672 KB Output is correct
5 Correct 137 ms 11260 KB Output is correct
6 Correct 2639 ms 30924 KB Output is correct
7 Correct 2793 ms 30824 KB Output is correct
8 Correct 2351 ms 30956 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 18 ms 9984 KB Output is correct
3 Correct 1162 ms 26168 KB Output is correct
4 Correct 998 ms 26164 KB Output is correct
5 Correct 101 ms 10744 KB Output is correct
6 Correct 2801 ms 30148 KB Output is correct
7 Correct 2786 ms 30052 KB Output is correct
8 Correct 2874 ms 30080 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 291 ms 23800 KB Output is correct
4 Correct 256 ms 23672 KB Output is correct
5 Correct 137 ms 11260 KB Output is correct
6 Correct 2639 ms 30924 KB Output is correct
7 Correct 2793 ms 30824 KB Output is correct
8 Correct 2351 ms 30956 KB Output is correct
9 Correct 11 ms 9856 KB Output is correct
10 Correct 18 ms 9984 KB Output is correct
11 Correct 1162 ms 26168 KB Output is correct
12 Correct 998 ms 26164 KB Output is correct
13 Correct 101 ms 10744 KB Output is correct
14 Correct 2801 ms 30148 KB Output is correct
15 Correct 2786 ms 30052 KB Output is correct
16 Correct 2874 ms 30080 KB Output is correct
17 Correct 118 ms 12280 KB Output is correct
18 Correct 25 ms 9984 KB Output is correct
19 Correct 1694 ms 26168 KB Output is correct
20 Correct 1696 ms 26168 KB Output is correct
21 Correct 202 ms 11004 KB Output is correct
22 Execution timed out 3096 ms 31140 KB Time limit exceeded
23 Halted 0 ms 0 KB -