Submission #762609

#TimeUsernameProblemLanguageResultExecution timeMemory
762609goodbyehanbyeolOrganizing the Best Squad (FXCUP4_squad)C++17
0 / 100
25 ms49556 KiB
#include "squad.h" #include <bits/stdc++.h> #define mabs(x) ((x)>0?(x):(-x)) using namespace std; typedef __int128 ll; ll gcd(ll x, ll y){ if(!y) return x; return gcd(y, x%y); } struct Frac{ ll a, b; Frac(){} Frac(ll x){ a=x, b=1; } Frac(ll _a, ll _b){ a = _a, b = _b; if(b<0) a=-a,b=-b; ll g = gcd(mabs(a), mabs(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; })); printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b, it.get(x).a, it.get(x).b, it.idx); 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){ ll X = _X, Y = _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, (long long)((atk[A1] + def[D1]) * X + (pop[A1] + pop[D1]) * Y)); if(A1 != D2) ret = max(ret, (long long)((atk[A1] + def[D2]) * X + (pop[A1] + pop[D2]) * Y)); if(A2 != D1) ret = max(ret, (long long)((atk[A2] + def[D1]) * X + (pop[A2] + pop[D1]) * Y)); if(A2 != D2) ret = max(ret, (long long)((atk[A2] + def[D2]) * X + (pop[A2] + pop[D2]) * Y)); return ret; }

Compilation message (stderr)

squad.cpp: In member function 'std::pair<Frac, int> LineContainer::query(Frac)':
squad.cpp:98:36: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'll' {aka '__int128'} [-Wformat=]
   98 |         printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
      |                                 ~~~^                                              ~~~~
      |                                    |                                                 |
      |                                    long long int                                     ll {aka __int128}
squad.cpp:98:43: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'll' {aka '__int128'} [-Wformat=]
   98 |         printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
      |                                        ~~~^                                             ~~~~
      |                                           |                                                |
      |                                           long long int                                    ll {aka __int128}
squad.cpp:98:50: warning: format '%lld' expects argument of type 'long long int', but argument 4 has type 'll' {aka '__int128'} [-Wformat=]
   98 |         printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
      |                                               ~~~^                                            ~~~
      |                                                  |                                              |
      |                                                  long long int                                  ll {aka __int128}
squad.cpp:98:55: warning: format '%lld' expects argument of type 'long long int', but argument 5 has type 'll' {aka '__int128'} [-Wformat=]
   98 |         printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
      |                                                    ~~~^                                            ~~~
      |                                                       |                                              |
      |                                                       long long int                                  ll {aka __int128}
squad.cpp:98:63: warning: format '%lld' expects argument of type 'long long int', but argument 6 has type 'll' {aka '__int128'} [-Wformat=]
   98 |         printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
      |                                                            ~~~^
      |                                                               |
      |                                                               long long int
   99 |                it.get(x).a, it.get(x).b, it.idx);
      |                ~~~~~~~~~~~                                     
      |                          |
      |                          ll {aka __int128}
squad.cpp:98:68: warning: format '%lld' expects argument of type 'long long int', but argument 7 has type 'll' {aka '__int128'} [-Wformat=]
   98 |         printf("Query answer: a %lld b %lld x %lld/%lld -> %lld/%lld (idx %d)\n", it.a, it.b, x.a, x.b,
      |                                                                 ~~~^
      |                                                                    |
      |                                                                    long long int
   99 |                it.get(x).a, it.get(x).b, it.idx);
      |                             ~~~~~~~~~~~                             
      |                                       |
      |                                       ll {aka __int128}
squad.cpp: In member function 'std::pair<Frac, int> segmentTree::query(int, int, int, int, int, Frac)':
squad.cpp:119:14: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
  119 |         auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
      |              ^~
squad.cpp:119:46: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
  119 |         auto p1 = query(i*2, l, m, s, e, x), p2 = query(i*2+1, m+1, r, s, e, x);
      |                                              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...