Submission #311165

#	Time	Username	Problem	Language	Result	Execution time	Memory
311165		FlowerOfSorrow	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	928 ms	55452 KiB

squad

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class L, class R> istream &operator>>(istream &in, pair<L, R> &p){ return in >> p.first >> p.second; }
template<class Tuple, size_t ...Is> void read_tuple(istream &in, Tuple &t, index_sequence<Is...>){ ((in >> get<Is>(t)), ...); }
template<class ...Args> istream &operator>>(istream &in, tuple<Args...> &t){ read_tuple(in, t, index_sequence_for<Args...>{}); return in; }
template<class ...Args, template<class...> class T> istream &operator>>(enable_if_t<!is_same_v<T<Args...>, string>, istream> &in, T<Args...> &arr){ for(auto &x: arr) in >> x; return in; }
template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){ return out << "(" << p.first << ", " << p.second << ")"; }
// template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){ return out << p.first << " " << p.second << "\n"; }
template<class Tuple, size_t ...Is> void print_tuple(ostream &out, const Tuple &t, index_sequence<Is...>){ ((out << (Is ? " " : "") << get<Is>(t)), ...); }
template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){ print_tuple(out, t, index_sequence_for<Args...>{}); return out << "\n"; }
template<class ...Args, template<class...> class T> ostream &operator<<(enable_if_t<!is_same_v<T<Args...>, string>, ostream> &out, const T<Args...> &arr){ for(auto &x: arr) out << x << " "; return out << "\n"; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngll(chrono::steady_clock::now().time_since_epoch().count());
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vl; typedef vector<double> vd; typedef vector<string> vs;
typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<int, ll> pil; typedef pair<ll, int> pli;
typedef vector<pii> vpii; typedef vector<pil> vpil; typedef vector<pli> vpli; typedef vector<pll> vpll;
template<class T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<class T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef tuple<int, int, int> tpl; typedef vector<tpl> vtpl;
 
template<class T = long long> struct point{
	T x, y;
	int ind;
	template<class U> point(const point<U> &otr): x(otr.x), y(otr.y), ind(otr.ind){ }
	template<class U = T, class V = T> point(U x = 0, V y = 0, int ind = -1): x(x), y(y), ind(ind){ }
	template<class U> explicit operator point<U>() const{ return point<U>(static_cast<U>(x), static_cast<U>(y)); }
	T operator*(const point &otr) const{ return x * otr.x + y * otr.y; }
	T operator^(const point &otr) const{ return x * otr.y - y * otr.x; }
	point operator+(const point &otr) const{ return {x + otr.x, y + otr.y}; }
	point &operator+=(const point &otr){ return *this = *this + otr; }
	point operator-(const point &otr) const{ return {x - otr.x, y - otr.y}; }
	point &operator-=(const point &otr){ return *this = *this - otr; }
	point operator-() const{ return {-x, -y}; }
#define scalarop_l(op) friend point operator op(const T &c, const point &p){ return {c op p.x, c op p.y}; }
	scalarop_l(+) scalarop_l(-) scalarop_l(*) scalarop_l(/)
#define scalarop_r(op) point operator op(const T &c) const{ return {x op c, y op c}; }
	scalarop_r(+) scalarop_r(-) scalarop_r(*) scalarop_r(/)
#define scalarapply(op) point &operator op(const T &c){ return *this = *this op c; }
	scalarapply(+=) scalarapply(-=) scalarapply(*=) scalarapply(/=)
#define compareop(op) bool operator op(const point &otr) const{ return tie(x, y) op tie(otr.x, otr.y); }
	compareop(>) compareop(<) compareop(>=) compareop(<=) compareop(==) compareop(!=)
#undef scalarop_l
#undef scalarop_r
#undef scalarapply
#undef compareop
	double norm() const{ return sqrt(x * x + y * y); }
	T squared_norm() const{ return x * x + y * y; }
	double arg() const{ return atan2(y, x); } // [-pi, pi]
	point<double> unit() const{ return point<double>(x, y) / norm(); }
	point perp() const{ return {-y, x}; }
	point<double> normal() const{ return perp().unit(); }
	point<double> rotate(const double &theta) const{ return point<double>(x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)); }
	point reflect_x() const{ return {x, -y}; }
	point reflect_y() const{ return {-x, y}; }
	point reflect(const point &o) const{ return {2 * o.x - x, 2 * o.y - y}; }
	bool operator||(const point &otr) const{ return !(*this ^ otr); }
};
template<class T> istream &operator>>(istream &in, point<T> &p){ return in >> p.x >> p.y; }
template<class T> ostream &operator<<(ostream &out, const point<T> &p){ return out << "(" << p.x << ", " << p.y << ")"; }
template<class T> double distance(const point<T> &p, const point<T> &q){ return (p - q).norm(); }
template<class T> T squared_distance(const point<T> &p, const point<T> &q){ return (p - q).squared_norm(); }
template<class T, class U, class V> T ori(const point<T> &p, const point<U> &q, const point<V> &r){ return (q - p) ^ (r - p); }
template<class IT> auto doubled_signed_area(IT begin, IT end){
	class iterator_traits<IT>::value_type s = 0, init = *begin;
	for(; begin != prev(end); ++ begin) s += *begin ^ *next(begin);
	return s + (*begin ^ init);
}
template<class T> bool is_sorted(const point<T> &origin, point<T> p, point<T> q, point<T> r){
	p -= origin, q -= origin, r -= origin;
	T x = p ^ r, y = p ^ q, z = q ^ r;
	return x >= 0 && y >= 0 && z >= 0 || x < 0 && (y >= 0 || z >= 0);
}
template<class T, class IT> bool is_sorted(const point<T> &origin, IT begin, IT end){
	for(int i = 0; i < end - begin - 2; ++ i) if(!is_sorted(origin, begin + i, begin + i + 1, begin + i + 2)) return false;
	return true;
}
template<class T = long long> struct line{
	point<T> p, d; // p + d*t
	template<class U = T, class V = T> line(point<U> p = {0, 0}, point<V> q = {0, 0}, bool Two_Points = true): p(p), d(Two_Points ? q - p : q){ }
	template<class U> line(point<U> d): p(), d(static_cast<point<T>>(d)){ }
	line(T a, T b, T c): p(a ? -c / a : 0, !a && b ? -c / b : 0), d(-b, a){ }
	template<class U> explicit operator line<U>() const{ return line<U>(point<U>(p), point<U>(d), false); }
	point<T> q() const{ return p + d; }
	bool degen() const{ return d == point<T>(); }
	tuple<T, T, T> coef() const{ return {d.y, -d.x, d.perp() * p}; } // d.y (X - p.x) - d.x (Y - p.y) = 0
	bool operator||(const line<T> &L) const{ return d || L.d; }
};
template<class T> bool on_line(const point<T> &p, const line<T> &L){
	if(L.degen()) return p == L.p;
	return (p - L.p) || L.d;
}
template<class T> bool on_ray(const point<T> &p, const line<T> &L){
	if(L.degen()) return p == L.p;
	auto a = L.p - p, b = L.q() - p;
	return (a || b) && a * L.d <= 0;
}
template<class T> bool on_segment(const point<T> &p, const line<T> &L){
	if(L.degen()) return p == L.p;
	auto a = L.p - p, b = L.q() - p;
	return (a || b) && a * b <= 0;
}
template<class T> double distance_to_line(const point<T> &p, const line<T> &L){
	if(L.degen()) return distance(p, L.p);
	return abs((p - L.p) ^ L.d) / L.d.norm();
}
template<class T> double distance_to_ray(const point<T> &p, const line<T> &L){
	if((p - L.p) * L.d <= 0) return distance(p, L.p);
	return distance_to_line(p, L);
}
template<class T> double distance_to_segment(const point<T> &p, const line<T> &L){
	if((p - L.p) * L.d <= 0) return distance(p, L.p);
	if((p - L.q()) * L.d >= 0) return distance(p, L.q());
	return distance_to_line(p, L);
}
template<class T> point<double> projection(const point<T> &p, const line<T> &L){ return static_cast<point<double>>(L.p) + (L.degen() ? point<double>() : (p - L.p) * L.d / L.d.norm() * static_cast<point<double>>(L.d)); }
template<class T> point<double> reflection(const point<T> &p, const line<T> &L){ return 2.0 * projection(p, L) - static_cast<point<double>>(p); }
template<class T> point<double> closest_point_on_segment(const point<T> &p, const line<T> &L){ return (p - L.p) * L.d <= 0 ? static_cast<point<double>>(L.p) : ((p - L.q()) * L.d >= 0 ? static_cast<point<double>>(L.q()) : projection(p, L)); }
template<int TYPE> struct EndpointChecker{ };
// For rays
template<> struct EndpointChecker<0>{ template<class T> bool operator()(const T& a, const T& b) const{ return true; } }; // For ray
// For closed end
template<> struct EndpointChecker<1>{ template<class T> bool operator()(const T& a, const T& b) const{ return a <= b; } }; // For closed end
// For open end
template<> struct EndpointChecker<2>{ template<class T> bool operator()(const T& a, const T& b) const{ return a < b; } }; // For open end
// Assumes parallel lines do not intersect
template<int LA, int LB, int RA, int RB, class T> pair<bool, point<double>> intersect_no_parallel_overlap(const line<T> &L, const line<T> &M){
	auto s = L.d ^ M.d;
	if(!s) return {false, point<double>()};
	auto ls = (M.p - L.p) ^ M.d, rs = (M.p - L.p) ^ L.d;
	if(s < 0) s = -s, ls = -ls, rs = -rs;
	bool intersect = EndpointChecker<LA>()(decltype(ls)(0), ls) && EndpointChecker<LB>()(ls, s) && EndpointChecker<RA>()(decltype(rs)(0), rs) && EndpointChecker<RB>()(rs, s);
	return {intersect, static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d)};
}
// Assumes parallel lines do not intersect
template<class T> pair<bool, point<double>> intersect_closed_segments_no_parallel_overlap(const line<T> &L, const line<T> &M){
	return intersect_no_parallel_overlap<1, 1, 1, 1>(L, M);
}
// Assumes nothing
template<class T> pair<bool, line<double>> intersect_closed_segments(const line<T> &L, const line<T> &M){
	auto s = L.d ^ M.d, ls = (M.p - L.p) ^ M.d;
	if(!s){
		if(ls) return {false, line<double>()};
		auto Lp = L.p, Lq = L.q(), Mp = M.p, Mq = M.q();
		if(Lp > Lq) swap(Lp, Lq);
		if(Mp > Mq) swap(Mp, Mq);
		line<double> res(max(Lp, Mp), min(Lq, Mq));
		return {res.d >= point<double>(), res};
	}
	auto rs = (M.p - L.p) ^ L.d;
	if(s < 0) s = -s, ls = -ls, rs = -rs;
	bool intersect = 0 <= ls && ls <= s && 0 <= rs && rs <= s;
	return {intersect, line<double>(static_cast<point<double>>(L.p) + 1.0 * ls / s * static_cast<point<double>>(L.d), point<double>())};
}
template<class T> double distance_between_rays(const line<T> &L, const line<T> &M){
	if(L || M){
		if(L.d * M.d >= 0 || (M.p - L.p) * M.d <= 0) return distance_to_line(L.p, M);
		else return distance(L.p, M.p);
	}
	else{
		if(intersect_no_parallel_overlap<1, 0, 1, 0, long long>(L, M).first) return 0;
		else return min(distance_to_ray(L.p, M), distance_to_ray(M.p, L));
	}
}
template<class T> double distance_between_segments(const line<T> &L, const line<T> &M){
	if(intersect_closed_segments(L, M).first) return 0;
	return min({distance_to_segment(L.p, M), distance_to_segment(L.q(), M), distance_to_segment(M.p, L), distance_to_segment(M.q(), L)});
}
template<class P> struct compare_by_angle{
	const P origin;
	compare_by_angle(const P &origin = P()): origin(origin){ }
	bool operator()(const P &p, const P &q) const{ return ori(origin, p, q) > 0; }
};
template<class It, class P> void sort_by_angle(It begin, It end, const P &origin){
	begin = partition(begin, end, [&origin](const decltype(*begin) &point){ return point == origin; });
	auto pivot = partition(begin, end, [&origin](const decltype(*begin) &point) { return point > origin; });
	compare_by_angle<P> cmp(origin);
	sort(begin, pivot, cmp), sort(pivot, end, cmp);
}
/* Short Descriptions
struct point{
	T x, y;
	int ind;
	double norm()
	T squared_norm()
	double arg()
	point<double> unit()
	point perp()
	point<double> normal()
	point<double> rotate(double theta)
	point reflect_x()
	point reflect_y()
	point reflect(point o)
	bool operator||(point otr)
};
double distance(point p, point q)
T squared_distance(point p, point q)
T ori(point p, point q, point r)
auto doubled_signed_area(IT begin, IT end)
bool is_sorted(point o, point p, point q, point r)
bool is_sorted(point o, IT begin, IT end)
struct line{
	point p, d; // p + d*t
	line(point p = {0, 0}, point<V> q = {0, 0}, bool Two_Points = true)
	// two_points: pass through p and q
	// else: pass through p, slope q
	line(point<U> d) // pass through origin, slope d
	line(T a, T b, T c) // declare with ax + by + c = 0
	point<T> q()
	bool degen()
	tuple<T, T, T> coef()// d.y (X - p.x) - d.x (Y - p.y) = 0
};
bool on_line(point, line)
bool on_ray(point, line)
bool on_segment(point, line)
double distance_to_line(point, line)
double distance_to_ray(point, line)
double distance_to_segment(point, line)
point<double> projection(point, line)
point<double> reflection(point, line)
point<double> closest_point_on_segment(point, line)
// Endpoints: (0: rays), (1: closed), (2: open)
// Assumes parallel lines do not intersect
pair<bool, point<double>> intersect_no_parallel_overlap<EP1, EP2, EP3, EP4>(line, line)
// Assumes parallel lines do not intersect
pair<bool, point<double>> intersect_closed_segments_no_parallel_overlap(line, line)
// Assumes nothing
pair<bool, line<double>> intersect_closed_segments(line, line)
double distance_between_rays(line, line)
double distance_between_segments(line, line)
struct compare_by_angle
void sort_by_angle(It begin, It end, const P &origin) */
 
template<class Polygon>
struct convex_hull: pair<Polygon, Polygon>{ // (Lower, Upper) type {0: both, 1: lower, 2: upper}
	int type;
	convex_hull(Polygon arr = Polygon(), int type = 0, bool is_sorted = false): type(type){
		if(!is_sorted) sort(arr.begin(), arr.end()), arr.erase(unique(arr.begin(), arr.end()), arr.end());;
#define ADDP(C, cmp) while((int)C.size() > 1 && ori(C[(int)C.size() - 2], p, C.back()) cmp 0) C.pop_back(); C.push_back(p);
		for(auto &p: arr){
			if(type < 2){ ADDP(this->first, >=) }
			if(!(type & 1)){ ADDP(this->second, <=) }
		}
		reverse(this->second.begin(), this->second.end());
	}
	Polygon get_hull() const{
		if(type) return type == 1 ? this->first : this->second;
		if(sz(this->first) <= 1) return this->first;
		Polygon res(this->first);
		res.insert(res.end(), ++ this->second.begin(), -- this->second.end());
		return res;
	}
	int min_element(const class Polygon::value_type &p) const{
		assert(p.y >= 0 && !this->first.empty());
		int low = 0, high = sz(this->first);
		while(high - low > 2){
			int mid1 = (2 * low + high) / 3, mid2 = (low + 2 * high) / 3;
			p * this->first[mid1] >= p * this->first[mid2] ? low = mid1 : high = mid2;
		}
		int res = low;
		for(int i = low + 1; i < high; i ++) if(p * this->first[res] > p * this->first[i]) res = i;
		return res;
	}
	int max_element(const class Polygon::value_type &p) const{
		assert(p.y >= 0 && !this->second.empty());
		int low = 0, high = sz(this->second);
		while(high - low > 2){
			int mid1 = (2 * low + high) / 3, mid2 = (low + 2 * high) / 3;
			p * this->second[mid1] <= p * this->second[mid2] ? low = mid1 : high = mid2;
		}
		int res = low;
		for(int i = low + 1; i < high; ++ i) if(p * this->second[res] < p * this->second[i]) res = i;
		return res;
	}
	Polygon linearize() const{
		if(type == 1) return this->first;
		if(type == 2){ Polygon res(this->second); reverse(res.begin(), res.end()); return res; }
		if(sz(this->first) <= 1) return this->first;
		Polygon res;
		res.reserve((int)this->first.size() + (int)this->second.size());
		merge(all(this->first), ++ this->second.rbegin(), -- this->second.rend(), back_inserter(res));
		return res;
	}
	convex_hull operator^(const convex_hull &otr) const{
		Polygon temp, A = linearize(), B = otr.linearize();
		temp.reserve((int)A.size() + (int)B.size());
		merge(A.begin(), A.end(), B.begin(), B.end(), back_inserter(temp));
		return {temp, type, true};
	}
	pair<Polygon, Polygon> get_boundary() const{
		Polygon L(this->first), R(this->second);
		for(int i = 1; i < (int)this->first.size(); ++ i) L[i] -= L[0];
		for(int i = 1; i < (int)this->second.size(); ++ i) R[i] -= R[0];
		return {L, R};
	}
	convex_hull operator+(const convex_hull &otr) const{
		assert(type == otr.type);
		compare_by_angle<class Polygon::value_type> cmp;
		convex_hull res;
		pair<Polygon, Polygon> A(this->get_boudnary()), B(otr.get_boudnary());
#define PROCESS(COND, X) \
if(COND && !A.X.empty() && !B.X.empty()){ \
	res.X.reserve((int)A.X.size() + (int)B.X.size()); \
	res.X.push_back(A.X.front() + B.X.front()); \
	merge(A.X.begin() + 1, A.X.end(), B.X.begin() + 1, B.X.end(), back_inserter(res.X)); \
	for(int i = 1; i < (int)res.X.size(); ++ i) res.X[i] += res.X[i - 1]; \
}
		PROCESS(type < 2, first)
		PROCESS(!(type & 1), second)
		return res;
	}
};
 
int n, na, nb;
vector<vector<convex_hull<vector<point<long long>>>>> CH(2); // CH[i][j]: i=0(attack), i=1(defence), j=0(best), j=1(second best)
void Init(vi A, vi D, vi P){
	n = sz(A);
	vector<point<ll>> a(n), d(n);
	for(int i = 0; i < n; ++ i){
		a[i] = {A[i], P[i]};
		d[i] = {D[i], P[i]};
		a[i].ind = d[i].ind = i;
	}
	for(int k = 0; k < 2; ++ k){
		CH[k].emplace_back(k ? d : a, 2);
		vi used(n);
		for(auto &p: CH[k][0].second){
			used[p.ind] = true;
		}
		vector<point<ll>> temp;
		for(int i = 0; i < n; ++ i){
			if(!used[i]){
				temp.push_back(k ? d[i] : a[i]);
			}
		}
		CH[k].emplace_back(temp, 2);
	}
	na = sz(CH[0][0].second), nb = sz(CH[1][0].second);
}
ll BestSquad(int X, int Y){
	int ia = CH[0][0].max_element({X, Y}), ib = CH[1][0].max_element({X, Y});
	auto eval = [&](int i, int j, int k){
		return CH[i][j].second[k] * point(X, Y);
	};
	if(CH[0][0].second[ia].ind == CH[1][0].second[ib].ind){
		ll res = max(eval(0, 0, ia) + max(eval(1, 0, (ib - 1 + nb) % nb), eval(1, 0, (ib + 1) % nb)), max(eval(0, 0, (ia - 1 + na) % na), eval(0, 0, (ia + 1) % na)) + eval(1, 0, ib));
		if(!CH[1][1].second.empty()){
			ctmax(res, eval(0, 0, ia) + eval(1, 1, CH[1][1].max_element({X, Y})));
		}
		if(!CH[0][1].second.empty()){
			ctmax(res, eval(0, 1, CH[0][1].max_element({X, Y})) + eval(1, 0, ib));
		}
		return res;
	}
	else{
		return eval(0, 0, ia) + eval(1, 0, ib);
	}
}
 
/*int main(){
	cin.tie(0)->sync_with_stdio(0);
	Init({3, 3, 5, 2, 1}, {2, 1, 1, 1, 4}, {5, 4, 3, 1, 2});
	cout << BestSquad(2, 5) << "\n";
	return 0;
}*/
 
/*
5
3 2 5
3 1 4
5 1 3
2 1 1
1 4 2
1
2 5
*/
 
////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

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