#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 = ll> struct point{
T x, y;
int ind;
// Modify this along with member variables
// point &operator=(const point &otr) { x = otr.x, y = otr.y, ind = otr.ind; return *this; }
template<class U> point(const point<U> &otr): x(otr.x), y(otr.y){ }
template<class U, class V> point(const pair<U, V> &p): x(p.first), y(p.second){ }
template<class U = T, class V = T> point(U x = 0, V y = 0): x(x), y(y){ }
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 point(x + otr.x, y + otr.y); }
point &operator+=(const point &otr){ return *this = *this + otr; }
point operator-(const point &otr) const{ return point(x - otr.x, y - otr.y); }
point &operator-=(const point &otr){ return *this = *this - otr; }
point operator*(const T &c) const{ return point(x * c, y * c); }
point &operator*=(const T &c) { return *this = *this * c; }
point operator/(const T &c) const{ return point(x / c, y / c); }
point &operator/=(const T &c) { return *this = *this / c; }
point operator-() const{ return point(-x, -y); }
bool operator<(const point &otr) const{ return tie(x, y) < tie(otr.x, otr.y); }
bool operator>(const point &otr) const{ return tie(x, y) > tie(otr.x, otr.y); }
bool operator<=(const point &otr) const{ return tie(x, y) <= tie(otr.x, otr.y); }
bool operator>=(const point &otr) const{ return tie(x, y) >= tie(otr.x, otr.y); }
bool operator==(const point &otr) const{ return tie(x, y) == tie(otr.x, otr.y); }
bool operator!=(const point &otr) const{ return tie(x, y) != tie(otr.x, otr.y); }
double norm() const{ return sqrt(x * x + y * y); }
T sqnorm() 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 point(-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 point(x, -y); }
point reflect_y() const{ return point(-x, y); }
};
template<class T> point<T> operator*(const T &c, const point<T> &p){ return point<T>(c * p.x, c * p.y); }
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 << pair<T, T>(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).sqnorm(); }
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 T> T doubled_signed_area(const vector<T> &arr){
T s = arr.back() ^ arr.front();
for(int i = 1; i < sz(arr); ++ i) s += arr[i - 1] ^ arr[i];
return s;
}
template<class T = ll> 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); }
line &operator=(const line &otr){ p = otr.p, d = otr.d; return *this; }
point<T> q() const{ return p + d; }
bool degen() const{ return d == point<T>(); }
tuple<T, T, T> coef(){ return {d.y, -d.x, d.perp() * p}; } // d.y (X - p.x) - d.x (Y - p.y) = 0
};
template<class T> bool parallel(const line<T> &L, const line<T> &M){ return !(L.d ^ M.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 == 0;
}
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(parallel(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, ll>(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 first, It last, const P &origin){
first = partition(first, last, [&origin](const decltype(*first) &point){ return point == origin; });
auto pivot = partition(first, last, [&origin](const decltype(*first) &point) { return point > origin; });
compare_by_angle<P> cmp(origin);
sort(first, pivot, cmp), sort(pivot, last, cmp);
}
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(all(arr)), arr.resize(unique(all(arr)) - arr.begin());
#define ADDP(C, cmp) while(sz(C) > 1 && ori(C[sz(C) - 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(all(this->second));
}
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(all(res)); return res; }
if(sz(this->first) <= 1) return this->first;
Polygon res;
res.reserve(sz(this->first) + sz(this->second));
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(sz(A) + sz(B));
merge(all(A), all(B), 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 < sz(this->first); ++ i) L[i] -= L[0];
for(int i = 1; i < sz(this->second); ++ 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(sz(A.X) + sz(B.X)); \
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 < sz(res.X); ++ 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<ll>>>>> 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);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
364 ms |
58856 KB |
Output is correct |
| 4 |
Correct |
364 ms |
58728 KB |
Output is correct |
| 5 |
Correct |
19 ms |
4512 KB |
Output is correct |
| 6 |
Correct |
288 ms |
64044 KB |
Output is correct |
| 7 |
Correct |
287 ms |
64052 KB |
Output is correct |
| 8 |
Correct |
286 ms |
64068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
6 ms |
884 KB |
Output is correct |
| 3 |
Correct |
508 ms |
49444 KB |
Output is correct |
| 4 |
Correct |
517 ms |
56496 KB |
Output is correct |
| 5 |
Correct |
23 ms |
2772 KB |
Output is correct |
| 6 |
Correct |
637 ms |
56052 KB |
Output is correct |
| 7 |
Correct |
656 ms |
56004 KB |
Output is correct |
| 8 |
Correct |
634 ms |
55960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
364 ms |
58856 KB |
Output is correct |
| 4 |
Correct |
364 ms |
58728 KB |
Output is correct |
| 5 |
Correct |
19 ms |
4512 KB |
Output is correct |
| 6 |
Correct |
288 ms |
64044 KB |
Output is correct |
| 7 |
Correct |
287 ms |
64052 KB |
Output is correct |
| 8 |
Correct |
286 ms |
64068 KB |
Output is correct |
| 9 |
Correct |
2 ms |
256 KB |
Output is correct |
| 10 |
Correct |
6 ms |
884 KB |
Output is correct |
| 11 |
Correct |
508 ms |
49444 KB |
Output is correct |
| 12 |
Correct |
517 ms |
56496 KB |
Output is correct |
| 13 |
Correct |
23 ms |
2772 KB |
Output is correct |
| 14 |
Correct |
637 ms |
56052 KB |
Output is correct |
| 15 |
Correct |
656 ms |
56004 KB |
Output is correct |
| 16 |
Correct |
634 ms |
55960 KB |
Output is correct |
| 17 |
Correct |
77 ms |
5416 KB |
Output is correct |
| 18 |
Correct |
7 ms |
1016 KB |
Output is correct |
| 19 |
Correct |
555 ms |
58728 KB |
Output is correct |
| 20 |
Correct |
556 ms |
58856 KB |
Output is correct |
| 21 |
Correct |
33 ms |
3008 KB |
Output is correct |
| 22 |
Correct |
873 ms |
64236 KB |
Output is correct |
| 23 |
Correct |
892 ms |
64192 KB |
Output is correct |
| 24 |
Correct |
876 ms |
64328 KB |
Output is correct |
