#include "squad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long 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 member function 'std::pair<Frac, int> segmentTree::query(int, int, int, int, int, Frac)':
squad.cpp:108:14: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
108 | auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
| ^~
squad.cpp:108:46: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
108 | auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
49492 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
50124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
49488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
49492 KB |
Output is correct |
| 2 |
Incorrect |
33 ms |
50124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
