//#include "squad.h"
//#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize ("trapv")
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define eb emplace_back
#define __V vector
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define oit ostream_iterator
#define mod 1000000007ll
#define print(x) for(auto i : (x)) cout << i << " ";cout << "\n";
#define printd(x) for(auto i : (x)) cout << i << " ";cout << #x << "\n";
using namespace std;
//using namespace __gnu_pbds;
void doin() {
cin.tie();
cout.tie();
ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
}
template<typename X, typename Y>
istream& operator>>(istream& in, pair<X, Y> &a) {
in >> a.first >> a.second;
return in;
}
template<typename T>
void getv(T& i) {
cin >> i;
}
template<typename T, typename ... Ns>
void getv(vector<T>& v, int n, Ns ... ns) {
v.resize(n);
for (auto& i : v)
getv(i, ns...);
}
template<typename T>
void getv1(T& i) {
cin >> i;
}
template<typename T, typename ... Ns>
void getv1(vector<T>& v, int n, Ns ... ns) {
v.resize(n + 1);
for (int i = 1; i <= n; i++)
getv1(v[i], ns...);
}
#ifdef _WIN32
#define getchar_unlocked() _getchar_nolock()
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
inline void getch(char &X) {
while (X = getchar_unlocked(), X < 33) {
;
}
}
inline void getstr(string &str) {
str.clear();
char cur;
while (cur = getchar_unlocked(), cur < 33) {
;
}
while (cur > 32) {
str += cur;
cur = getchar_unlocked();
}
}
template<typename T> inline bool sc(T &num) {
bool neg = 0;
int c;
num = 0;
while (c = getchar_unlocked(), c < 33) {
if (c == EOF)
return false;
}
if (c == '-') {
neg = 1;
c = getchar_unlocked();
}
for (; c > 47; c = getchar_unlocked())
num = num * 10 + c - 48;
if (neg)
num *= -1;
return true;
}
template<typename a, typename b>
void minq(a& X, b Y) {
if (X > Y)
X = Y;
}
template<typename a, typename b>
void maxq(a& X, b Y) {
if (X < Y)
X = Y;
}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef ll _I;
typedef pair<_I, _I> pi;
typedef pair<ld, ld> pd;
typedef map<_I, _I> mii;
typedef __V <_I> vi;
typedef __V <char> vc;
typedef __V <string> vs;
typedef __V <ld> vd;
typedef __V <vd> vvd;
typedef __V <pi> vpi;
typedef __V <__V<_I>> vvi;
typedef __V <__V<char>> vvc;
typedef __V <__V<pi>> vvpi;
using AntonTsypko = void;
using arsijo = AntonTsypko;
using god = arsijo;
//store differences, not the elements for rsq in fenwick or array(for write-only)
//Sum Over Subsets + inclusion-exclusion is a thing! (Solved div1E (383E) using it!)
//SQRT-heuristic divide items into groups: >sqrt and <=sqrt and do something according to group(eg. trie for one, z-func for other) - 1202E
//f-e+v=2
uniform_real_distribution<double> double_dist(0, 1);
uniform_int_distribution<int> dist(31, 55);
//WHEN DOING MODULAR SUBTRACTION ALWAYS **ALWAYS** ADD MOD
//don't use AVX at AtCoder(=RE)
//Trie: MAXDEPTH!=MAXSIZE
//suspiciously big numbers? use python, seriosly you don't wanna waste your time if it overflows
//MULTISET NOT SET
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//SQRT IS PROBABLY THE ANSWER
//SET TO ZERO
//typedef tree<int, null_type, greater<int>, rb_tree_tag,
// tree_order_statistics_node_update> ordered_set; // order_of_key, find_by_order
using vec = complex<ll>;
#define x real()
#define y imag()
ll dot(vec a, vec b) {
return (conj(a) * b).x;
}
ll cross(vec a, vec b) {
return (conj(a) * b).y;
}
using vvec = vector<vec>;
struct maxhull {
bool better(const vec &v, const vec &a, const vec &b) const {
return dot(v, a) > dot(v, b) || (dot(v, a) == dot(v, b) && a.y < b.y);
}
vvec pts, hulla, hullb;
bool to_remove(vvec &hull) {
int n = hull.size();
if(n < 3) return false;
return cross(hull[n-2]-hull[n-3], hull[n-1]-hull[n-2]) > 0;
}
void upperhull(vvec &pts, vvec& hull, vvec &dump) {
sort(all(pts), [](const vec &a, const vec &b) {
return pi(a.x, a.y) < pi(b.x, b.y);
});
for(auto i : pts) {
while(to_remove(hull)) {
swap(hull.back(), hull[hull.size()-2]);
dump.pb(hull.back());
hull.pop_back();
}
hull.pb(i);
}
}
void init() {
vvec dump, dumpb;
upperhull(pts, hulla, dump);
upperhull(dump, hullb, dumpb);
}
pair<vec, vec> query(vvec &hull, vec v) {
int lo = 0, hi = hull.size()-1, a, b;
while(hi-lo>3) {
a = lo + (hi-lo+1)/3;
b = hi - (hi-lo+1)/3;
if(better(v, hull[b], hull[a]))
lo = a;
else
hi = b;
}
pair<vec, vec> ans = {vec(0, 0), vec(0, 0)};
for(int i = max(0, lo-3); i <= min((int)hull.size()-1, hi+3); i++) {
if(better(v, hull[i], ans.first)) {
ans.second = ans.first;
ans.first = hull[i];
} else if(better(v, hull[i], ans.second))
ans.second = hull[i];
}
return ans;
}
pair<vec, vec> query(vec v) {
pair<vec, vec> a = query(hulla, v);
pair<vec, vec> b = query(hullb, v);
if(better(v, b.first, a.second))
a.second = b.first;
return a;
}
};
int n;
vector<ll> p;
maxhull dmg, def;
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
n = A.size();
for(auto i : P) p.pb(i);
for(int i = 0; i < n; i++)
dmg.pts.pb(vec(A[i], P[i]));
for(int i = 0; i < n; i++)
def.pts.pb(vec(D[i], P[i]));
dmg.init();
def.init();
sort(all(p), greater<ll>());
// for(auto i : m.hull)
// cout << i << "\n";
}
long long BestSquad(int X, int Y){
ll ans = 0;
pair<vec, vec> a = dmg.query(vec(X, Y));
pair<vec, vec> b = def.query(vec(X, Y));
if(a.first.y != b.first.y) {
ans = dot(a.first+b.first, vec(X, Y));
} else {
ans = dot(a.first+b.second, vec(X, Y));
maxq(ans, dot(a.second+b.first, vec(X, Y)));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
373 ms |
49460 KB |
Output is correct |
| 4 |
Correct |
390 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
20 ms |
3184 KB |
Output is correct |
| 6 |
Correct |
310 ms |
44764 KB |
Output is correct |
| 7 |
Correct |
298 ms |
44720 KB |
Output is correct |
| 8 |
Correct |
300 ms |
44848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
760 KB |
Output is correct |
| 3 |
Correct |
601 ms |
46640 KB |
Output is correct |
| 4 |
Correct |
614 ms |
46620 KB |
Output is correct |
| 5 |
Correct |
24 ms |
2420 KB |
Output is correct |
| 6 |
Correct |
670 ms |
43340 KB |
Output is correct |
| 7 |
Correct |
659 ms |
43228 KB |
Output is correct |
| 8 |
Correct |
660 ms |
42972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
504 KB |
Output is correct |
| 3 |
Correct |
373 ms |
49460 KB |
Output is correct |
| 4 |
Correct |
390 ms |
49500 KB |
Output is correct |
| 5 |
Correct |
20 ms |
3184 KB |
Output is correct |
| 6 |
Correct |
310 ms |
44764 KB |
Output is correct |
| 7 |
Correct |
298 ms |
44720 KB |
Output is correct |
| 8 |
Correct |
300 ms |
44848 KB |
Output is correct |
| 9 |
Correct |
3 ms |
376 KB |
Output is correct |
| 10 |
Correct |
6 ms |
760 KB |
Output is correct |
| 11 |
Correct |
601 ms |
46640 KB |
Output is correct |
| 12 |
Correct |
614 ms |
46620 KB |
Output is correct |
| 13 |
Correct |
24 ms |
2420 KB |
Output is correct |
| 14 |
Correct |
670 ms |
43340 KB |
Output is correct |
| 15 |
Correct |
659 ms |
43228 KB |
Output is correct |
| 16 |
Correct |
660 ms |
42972 KB |
Output is correct |
| 17 |
Correct |
82 ms |
5368 KB |
Output is correct |
| 18 |
Correct |
9 ms |
888 KB |
Output is correct |
| 19 |
Correct |
641 ms |
49720 KB |
Output is correct |
| 20 |
Correct |
636 ms |
49632 KB |
Output is correct |
| 21 |
Correct |
33 ms |
2804 KB |
Output is correct |
| 22 |
Correct |
844 ms |
45760 KB |
Output is correct |
| 23 |
Correct |
821 ms |
45520 KB |
Output is correct |
| 24 |
Correct |
938 ms |
45568 KB |
Output is correct |
