oj.uz

Submission #149113

# Submission time Handle Problem Language Result Execution time Memory
149113 2019-09-01T05:45:52 Z CHT를 사랑하는 모임(#3587, moonrabbit2, Retro3014, gs18115) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 30976 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);
		}
		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:154: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 278 ms 23800 KB Output is correct
4 Correct 248 ms 23932 KB Output is correct
5 Correct 104 ms 11000 KB Output is correct
6 Correct 2164 ms 30696 KB Output is correct
7 Correct 2035 ms 30952 KB Output is correct
8 Correct 2158 ms 30976 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 19 ms 9984 KB Output is correct
3 Correct 1000 ms 25912 KB Output is correct
4 Correct 1014 ms 26036 KB Output is correct
5 Correct 92 ms 10744 KB Output is correct
6 Correct 2333 ms 30120 KB Output is correct
7 Correct 2606 ms 30120 KB Output is correct
8 Correct 2437 ms 30120 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 278 ms 23800 KB Output is correct
4 Correct 248 ms 23932 KB Output is correct
5 Correct 104 ms 11000 KB Output is correct
6 Correct 2164 ms 30696 KB Output is correct
7 Correct 2035 ms 30952 KB Output is correct
8 Correct 2158 ms 30976 KB Output is correct
9 Correct 11 ms 9728 KB Output is correct
10 Correct 19 ms 9984 KB Output is correct
11 Correct 1000 ms 25912 KB Output is correct
12 Correct 1014 ms 26036 KB Output is correct
13 Correct 92 ms 10744 KB Output is correct
14 Correct 2333 ms 30120 KB Output is correct
15 Correct 2606 ms 30120 KB Output is correct
16 Correct 2437 ms 30120 KB Output is correct
17 Correct 119 ms 12280 KB Output is correct
18 Correct 28 ms 9984 KB Output is correct
19 Correct 1678 ms 26164 KB Output is correct
20 Correct 1611 ms 26164 KB Output is correct
21 Correct 178 ms 11000 KB Output is correct
22 Execution timed out 3099 ms 30952 KB Time limit exceeded
23 Halted 0 ms 0 KB -