Submission #150887

#	Time	Username	Problem	Language	Result	Execution time	Memory
150887		gs14004	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1210 ms	87792 KiB

squad

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
 
#include "squad.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
const int MAXN = 300005;
 
struct pi{
	int first, second, idx, cnt;
	bool operator<(const pi &q)const{
		return make_pair(first, second) < make_pair(q.first, q.second);
	}
};
 
lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}
 
struct convex_hull{
	vector<pi> V;
	void init(vector<pi> inp){
		for(auto &i : inp){
			while(sz(V) >= 2 && ccw(V[sz(V) - 2], V.back(), i) > 0) V.pop_back();
			V.push_back(i);
		}
	}
	pair<lint, int> get(int x, int y){
		lint cur = -5e18;
		int cnt = 0;
		int pos = -1;
		if(sz(V)){
			int s = 0, e = sz(V) - 1;
			while(s != e){
				int m = (s+e)/2;
				lint qr1 = 1ll * V[m].first * x + 1ll * V[m].second * y;
				lint qr2 = 1ll * V[m+1].first * x + 1ll * V[m+1].second * y;
				if(qr1 < qr2) s = m + 1;
				else e = m;
			}
			for(int i=s; i<sz(V) && i<s+2; i++){
				lint qr = 1ll * V[i].first * x + 1ll * V[i].second * y;
				if(qr > cur){
					cur = qr;
					cnt = 0;
					pos = V[i].idx;
				}
				if(qr == cur) cnt += V[i].cnt;
			}
		}
		if(cnt >= 2) pos = -1;
		return make_pair(cur, pos);
	}
}X, Y, FUCKX[MAXN], FUCKY[MAXN];
 
int N;
vector<pi> v, w;
 
vector<pi> norm(vector<pi> v){
	sort(v.begin(), v.end());
	vector<pi> w;
	for(int i=0; i<sz(v); ){
		int e = i;
		while(e < sz(v) && make_pair(v[i].first, v[i].second) == make_pair(v[e].first, v[e].second)) e++;
		w.push_back({v[i].first, v[i].second, v[i].idx, e - i});
		i = e;
	}
	return w;
}
 
int revX[MAXN], revY[MAXN];
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	N = sz(A);
	for(int i=0; i<N; i++){
		v.push_back({A[i], P[i], i, 1});
		w.push_back({D[i], P[i], i, 1});
	}
	v = norm(v);
	w = norm(w);
	X.init(v);
	Y.init(w);
	for(int i=0; i<sz(v); i++) revX[v[i].idx] = i;
	for(int i=0; i<sz(w); i++) revY[w[i].idx] = i;
	for(int i=0; i<sz(X.V); i++){
		int l = X.V[max(i - 1, 0)].idx;
		int r = X.V[min(i + 1, sz(X.V) - 1)].idx;
		l = revX[l];
		r = revX[r];
		vector<pi> fuck;
		for(int j=l; j<=r; j++){
			if(v[j].idx != X.V[i].idx) fuck.push_back(v[j]);
		}
		FUCKX[X.V[i].idx].init(fuck);
	}
	for(int i=0; i<sz(Y.V); i++){
		int l = Y.V[max(i - 1, 0)].idx;
		int r = Y.V[min(i + 1, sz(Y.V) - 1)].idx;
		l = revY[l];
		r = revY[r];
		vector<pi> fuck;
		for(int j=l; j<=r; j++){
			if(w[j].idx != Y.V[i].idx) fuck.push_back(w[j]);
		}
		FUCKY[Y.V[i].idx].init(fuck);
	}
}
 
long long BestSquad(int sex, int sey){
	auto qr1 = X.get(sex, sey);
	auto qr2 = Y.get(sex, sey);
	if(qr1.second < 0 || qr2.second < 0 || qr1.second != qr2.second) return qr1.first + qr2.first;
	lint ret = -5e18;
	ret = max(ret, qr1.first + FUCKY[qr1.second].get(sex, sey).first);
	ret = max(ret, qr2.first + FUCKX[qr2.second].get(sex, sey).first);
	return ret;
}

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53