oj.uz

Submission #229273

# Submission time Handle Problem Language Result Execution time Memory
229273 2020-05-04T03:43:20 Z 534351 Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 746 ms 57952 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 307 ms 56680 KB Output is correct
4 Correct 305 ms 56624 KB Output is correct
5 Correct 20 ms 4000 KB Output is correct
6 Correct 253 ms 56620 KB Output is correct
7 Correct 253 ms 56680 KB Output is correct
8 Correct 259 ms 56624 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 452 ms 54484 KB Output is correct
4 Correct 466 ms 54668 KB Output is correct
5 Correct 23 ms 2652 KB Output is correct
6 Correct 547 ms 55596 KB Output is correct
7 Correct 545 ms 55456 KB Output is correct
8 Correct 540 ms 55336 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 307 ms 56680 KB Output is correct
4 Correct 305 ms 56624 KB Output is correct
5 Correct 20 ms 4000 KB Output is correct
6 Correct 253 ms 56620 KB Output is correct
7 Correct 253 ms 56680 KB Output is correct
8 Correct 259 ms 56624 KB Output is correct
9 Correct 5 ms 256 KB Output is correct
10 Correct 9 ms 896 KB Output is correct
11 Correct 452 ms 54484 KB Output is correct
12 Correct 466 ms 54668 KB Output is correct
13 Correct 23 ms 2652 KB Output is correct
14 Correct 547 ms 55596 KB Output is correct
15 Correct 545 ms 55456 KB Output is correct
16 Correct 540 ms 55336 KB Output is correct
17 Correct 76 ms 5368 KB Output is correct
18 Correct 9 ms 1024 KB Output is correct
19 Correct 497 ms 57952 KB Output is correct
20 Correct 509 ms 57952 KB Output is correct
21 Correct 30 ms 2760 KB Output is correct
22 Correct 746 ms 56880 KB Output is correct
23 Correct 741 ms 56752 KB Output is correct
24 Correct 695 ms 56988 KB Output is correct