#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
struct Frac{
ll a, b;
Frac(){}
Frac(ll x){
a=x, b=1;
}
Frac(ll _a, ll _b){
a = _a, b = abs(_b);
ll g = __gcd(a, b);
a /= g, b /= g;
}
Frac operator+(const Frac &r)const{
return Frac(a*r.b+b*r.a, b*r.b);
}
Frac operator*(const Frac &r)const{
return Frac(a*r.a, b*r.b);
}
Frac operator/(const Frac &r)const{
return Frac(a*r.b, b*r.a);
}
bool operator<(Frac r)const{
if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b < b*r.a;
return val() < r.val();
}
bool operator<=(Frac r)const{
if(max({a, b, r.a, r.b}) <= 3e9) return a*r.b <= b*r.a;
return val() <= r.val();
}
bool operator==(Frac &r)const{
return a==r.a && b==r.b;
}
long double val()const{
return (long double)(a) / b;
}
};
struct Line{
ll a, b; Frac start; int idx;
Line(){}
Line(ll a, ll b): a(a), b(b){start = 0;}
Line(ll a, ll b, int idx): a(a), b(b), idx(idx){start = 0;}
Line(Frac start): start(start){}
bool operator<(const Line &r)const{
if(a == r.a) return b < r.b;
return a < r.a;
}
Frac get(Frac x){
return x*a+b;
}
Frac cross(Line &r)const{
return Frac(b-r.b)/Frac(r.a-a);
}
};
struct LineContainer{
vector<Line> vec;
LineContainer(){}
void update(Line p){
while(!vec.empty() && vec.back().a == p.a && vec.back().b == p.b) vec.pop_back();
while((int)vec.size() > 1 && vec[(int)vec.size()-2].cross(p) <= vec[(int)vec.size()-2].cross(vec.back()))
vec.pop_back();
if(!vec.empty()) p.start = vec.back().cross(p);
vec.push_back(p);
}
pair<Frac, int> query(Frac x){
auto it = *prev(upper_bound(vec.begin(), vec.end(), Line(Frac(x)), [&](Line a, Line b){
return a.start < b.start;
}));
return make_pair(it.get(x), it.idx);
}
};
struct segmentTree{
LineContainer tree[1<<20];
void init(int i, int l, int r, Line *lines){
for(int j=l; j<=r; j++) tree[i].update(lines[j]);
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m, lines);
init(i*2+1, m+1, r, lines);
}
pair<Frac, int> query(int i, int l, int r, int s, int e, Frac x){
if(r<s || e<l) return make_pair(Frac(0, 1), 0);
if(s<=l && r<=e) return tree[i].query(x);
int m = (l+r)>>1;
auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
// printf("%d %d %d %d %d %lld/%lld -> %lld/%lld (%d), %lld/%lld (%d)\n", i,l,r,s,e,x.a,x.b,p1.first.a,
// p1.first.b,p1.second,p2.first.a,p2.first.b,p2.second);
return max(query(i*2, l, m, s, e, x), query(i*2+1, m+1, r, s, e, x));
}
} treeA, treeD;
int n, dcond;
ll atk[300002], def[300002], pop[300002];
Line vecA[300002], vecD[300002];
int idxA[300002], idxD[300002];
void Init(vector<int> A, vector<int> D, vector<int> P){
n = (int)A.size(), dcond = 1;
for(int i=1; i<=n; i++){
atk[i] = A[i-1];
def[i] = D[i-1];
pop[i] = P[i-1];
if(def[i] != 1) dcond = 0;
}
for(int i=1; i<=n; i++){
vecA[i] = Line(pop[i]-atk[i], atk[i], i);
vecD[i] = Line(pop[i]-def[i], def[i], i);
}
sort(vecA+1, vecA+n+1);
sort(vecD+1, vecD+n+1);
for(int i=1; i<=n; i++){
idxA[vecA[i].idx] = i;
idxD[vecD[i].idx] = i;
}
treeA.init(1, 1, n, vecA);
treeD.init(1, 1, n, vecD);
}
long long BestSquad(int X, int Y){
int A1 = treeA.query(1, 1, n, 1, n, Frac(Y, X+Y)).second;
int A2 = max(treeA.query(1, 1, n, 1, idxA[A1]-1, Frac(Y, X+Y)),
treeA.query(1, 1, n, idxA[A1]+1, n, Frac(Y, X+Y))).second;
int D1 = treeD.query(1, 1, n, 1, n, Frac(Y, X+Y)).second;
int D2 = max(treeD.query(1, 1, n, 1, idxD[D1]-1, Frac(Y, X+Y)),
treeD.query(1, 1, n, idxD[D1]+1, n, Frac(Y, X+Y))).second;
long long ret = 0;
if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
return ret;
}
Compilation message
squad.cpp: In constructor 'Frac::Frac(ll, ll)':
squad.cpp:15:27: error: call of overloaded 'abs(ll&)' is ambiguous
15 | a = _a, b = abs(_b);
| ^
In file included from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from squad.cpp:2:
/usr/include/stdlib.h:840:12: note: candidate: 'int abs(int)'
840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
| ^~~
In file included from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from squad.cpp:2:
/usr/include/c++/10/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
79 | abs(long double __x)
| ^~~
/usr/include/c++/10/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
75 | abs(float __x)
| ^~~
/usr/include/c++/10/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
71 | abs(double __x)
| ^~~
/usr/include/c++/10/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
61 | abs(long long __x) { return __builtin_llabs (__x); }
| ^~~
/usr/include/c++/10/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
56 | abs(long __i) { return __builtin_labs(__i); }
| ^~~
squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:153:82: error: no matching function for call to 'max(long long int&, ll)'
153 | if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
squad.cpp:153:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
153 | if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
squad.cpp:153:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
153 | if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
squad.cpp:153:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
153 | if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
squad.cpp:153:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
153 | if(A1 != D1) ret = max(ret, (atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y);
| ^
squad.cpp:154:82: error: no matching function for call to 'max(long long int&, ll)'
154 | if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
squad.cpp:154:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
154 | if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
squad.cpp:154:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
154 | if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
squad.cpp:154:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
154 | if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
squad.cpp:154:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
154 | if(A1 != D2) ret = max(ret, (atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y);
| ^
squad.cpp:155:82: error: no matching function for call to 'max(long long int&, ll)'
155 | if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
squad.cpp:155:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
155 | if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
squad.cpp:155:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
155 | if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
squad.cpp:155:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
155 | if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
squad.cpp:155:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
155 | if(A2 != D1) ret = max(ret, (atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y);
| ^
squad.cpp:156:82: error: no matching function for call to 'max(long long int&, ll)'
156 | if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
squad.cpp:156:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
156 | if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/vector:60,
from squad.h:2,
from squad.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
squad.cpp:156:82: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'll' {aka '__int128'})
156 | if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
squad.cpp:156:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
156 | if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from squad.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
squad.cpp:156:82: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
156 | if(A2 != D2) ret = max(ret, (atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y);
| ^
