Submission #229273

#	Time	Username	Problem	Language	Result	Execution time	Memory
229273		534351	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	746 ms	57952 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef pair<pll, int> plp;
typedef vector<plp> vpp;
typedef pair<pll, pll> ppp;

pair<vpp, vpp> ha, hb;

int ccw(pll a, pll b, pll c)
{
    a.fi -= b.fi; a.se -= b.se;
    c.fi -= b.fi; c.se -= b.se;
    ll cp = a.fi * c.se - a.se * c.fi;
    if (cp > 0) return 1;
    if (cp < 0) return -1;
    return 0;
}
pair<vpp, vpp> build(vpp v)
{
    pair<vpp, vpp> res;
    sort(ALL(v), greater<plp>());
    for (plp p : v)
    {
        while(SZ(res.fi) >= 2 && ccw(res.fi[SZ(res.fi) - 2].fi, res.fi.back().fi, p.fi) != -1)
        {
            res.se.PB(res.fi.back());
            res.fi.pop_back();
        }
        res.fi.PB(p);
    }
    v = res.se; res.se.clear();
    sort(ALL(v), greater<plp>());
    for (plp p : v)
    {
        while(SZ(res.se) >= 2 && ccw(res.se[SZ(res.se) - 2].fi, res.se.back().fi, p.fi) != -1)
        {
            res.se.pop_back();
        }
        res.se.PB(p);
    }
    return res;
}
void Init(vi a, vi b, vi c)
{
    int n = SZ(a);
    vpp nums;
    FOR(i, 0, n)
    {
        nums.PB({{a[i], c[i]}, i});
    }
    ha = build(nums);
    nums.clear();
    FOR(i, 0, n)
    {
        nums.PB({{b[i], c[i]}, i});
    }
    hb = build(nums);
    return;
}
pll eval(plp line, pll p)
{
    return {line.fi.fi * p.fi + line.fi.se * p.se, line.se};
}
ppp query(pair<vpp, vpp> &hull, pll p)
{
    //query this hull for the largest & second largest value of dot product with p
    ppp res = {{0, 0}, {0, 0}};
    int lo = 0, hi = SZ(hull.fi) - 1;
    while(hi > lo)
    {
        int mid = (hi + lo) >> 1;
        if (eval(hull.fi[mid], p) < eval(hull.fi[mid + 1], p)) lo = mid + 1;
        else hi = mid;
    }
    res.fi = eval(hull.fi[lo], p);
    if (lo + 1 != SZ(hull.fi))
    {
        ckmax(res.se, eval(hull.fi[lo + 1], p));
    }
    if (lo - 1 != -1)
    {
        ckmax(res.se, eval(hull.fi[lo - 1], p));
    }
    if (!hull.se.empty())
    {
        lo = 0; hi = SZ(hull.se) - 1;
        while(hi > lo)
        {
            int mid = (hi + lo) >> 1;
            if (eval(hull.se[mid], p) < eval(hull.se[mid + 1], p)) lo = mid + 1;
            else hi = mid;
        }
        ckmax(res.se, eval(hull.se[lo], p));
    }
    return res;
}

ll BestSquad(int c1, int c2)
{
    pll p = {c1, c2};
    auto a = query(ha, p), b = query(hb, p);
    if (a.fi.se != b.fi.se)
    {
        return a.fi.fi + b.fi.fi;
    }
    return max(a.fi.fi + b.se.fi, a.se.fi + b.fi.fi);
}

• Subtask 1: 19 / 19
• Subtask 2: 28 / 28
• Subtask 3: 53 / 53