Submission #151018

#TimeUsernameProblemLanguageResultExecution timeMemory
151018bogdan10bosOrganizing the Best Squad (FXCUP4_squad)C++17
47 / 100
2445 ms41844 KiB
#include "squad.h" #include <bits/stdc++.h> #pragma GCC optimize ("Ofast") typedef double LD; using namespace std; const LD eps = 1e-6; class LiChao { public: struct Line { LD a = 0, b = 0; int id = 0; Line() { ; } Line(LD _a, LD _b, int _id) { a = _a, b = _b, id = _id; } LD operator()(LD x) { return a * x + b; } const bool operator== (const Line &l) const { return (id == l.id); } }; struct Node { Line unu, doi; Node *l, *r; Node(Line a, Line b, Node *_l, Node *_r) { unu = a, doi = b, l = _l, r = _r; } }; Line df; Node *root; LiChao() { df = Line(0, 0, -1); root = new Node(df, df, 0, 0); } void insert(Node *&nod, LD st, LD dr, Line l) { if(l == df) return; if(nod == 0) { nod = new Node(l, df, 0, 0); return; } LD mij = (st + dr) / 2.0; if(nod->unu(mij) < l(mij)) { swap(nod->unu, l); swap(nod->doi, l); } else if(nod->doi(mij) < l(mij)) swap(nod->doi, l); if(l == df) return; if(l(st) > max(nod->unu(st), nod->doi(st))) insert(nod->l, st, mij, l); if(l(dr) > max(nod->unu(dr), nod->doi(dr))) insert(nod->r, mij, dr, l); } void insert(LD a, LD b, int id) { insert(root, 0, 1e9, Line(a, b, id)); } pair<Line, Line> query(Node *nod, LD st, LD dr, LD x) { if(nod == 0) return {df, df}; Line unu = nod->unu, doi = nod->doi; if(unu(x) < doi(x)) swap(unu, doi); pair<Line, Line> nxt = {df, df}; LD mij = st + (dr - st) / 2; if(x < mij) nxt = query(nod->l, st, mij, x); else nxt = query(nod->r, mij, dr, x); if(nxt.first(x) > unu(x)) { swap(doi, nxt.first); swap(unu, doi); } else if(nxt.first(x) > doi(x)) swap(doi, nxt.first); if(nxt.second(x) > unu(x)) { swap(doi, nxt.second); swap(unu, doi); } else if(nxt.second(x) > doi(x)) swap(doi, nxt.second); return {unu, doi}; } pair<Line, Line> query(LD x) { return query(root, 0, 1e9, x); } }; LiChao att, def; vector<int> AA, DD, PP; void Init(vector<int> A, vector<int> D, vector<int> P) { AA = A, DD = D, PP = P; int N = A.size(); for(int i = 0; i < N; i++) { att.insert(A[i], P[i], i); def.insert(D[i], P[i], i); } } long long calc(int a, int d, int X, int Y) { if(a == d) return -1; long long ans = 1LL * X * (AA[a] + DD[d]) + 1LL * Y * (PP[a] + PP[d]); return ans; } long long BestSquad(int X, int Y) { LD frac = LD(X) / LD(Y); auto at = att.query(frac); auto df = def.query(frac); vector<int> ids; ids.push_back(at.first.id); ids.push_back(at.second.id); ids.push_back(df.first.id); ids.push_back(df.second.id); long long ans = -1; ans = max(ans, calc(ids[0], ids[2], X, Y)); ans = max(ans, calc(ids[1], ids[2], X, Y)); ans = max(ans, calc(ids[0], ids[3], X, Y)); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...