oj.uz

Submission #148720

# Submission time Handle Problem Language Result Execution time Memory
148720 2019-09-01T04:59:45 Z mit한의대지망생(#3602, TAMREF, imeimi2000, suzy) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 937 ms 54568 KB 
#include "squad.h"
#include <algorithm>
#include <vector>
#include <set>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<llong, llong> pll;

int ccw(pll a, pll b, pll c) {
    llong x1 = b.fs - a.fs, y1 = b.se - a.se;
    llong x2 = c.fs - b.fs, y2 = c.se - b.se;
    llong val = x1 * y2 - x2 * y1;
    if (val > 0) return 1;
    if (val < 0) return -1;
    return 0;
}

struct convex_hull {
    vector<pair<pll, int>> ps;
    void add(llong x, llong y, int i) {
        ps.emplace_back(pll(x, y), i);
    }
    void init() {
        sort(ps.begin(), ps.end());
        vector<pair<pll, int>> tp;
        for (auto i : ps) {
            while (!tp.empty() && tp.back().fs.se <= i.fs.se)
                tp.pop_back();
            tp.push_back(i);
        }
        ps.clear();
        for (auto i : tp) {
            int sz;
            while ((sz = ps.size()) > 1 && ccw(ps[sz - 2].fs, ps[sz - 1].fs, i.fs) >= 0)
                ps.pop_back();
            ps.push_back(i);
        }
    }
    vector<pair<pll, int>> get(llong x, llong y) {
        vector<pair<pll, int>> ret;
        int s = 0, e = (int)ps.size() - 1;
        while (s < e) {
            int m = (s + e) / 2;
            llong L = ps[m].fs.fs * x + ps[m].fs.se * y;
            llong R = ps[m + 1].fs.fs * x + ps[m + 1].fs.se * y;
            if (L < R) s = m + 1;
            else e = m;
        }
        for (int i = max(0, s - 1); i <= e + 1 && i < ps.size(); ++i) ret.push_back(ps[i]);
        return ret;
    }
} as1, as2, ds1, ds2;

int usedA[300000];
int usedD[300000];
void Init(vector<int> A, vector<int> D, vector<int> P) {
    int n = A.size();
    for (int i = 0; i < n; ++i) {
        as1.add(A[i], P[i], i);
        ds1.add(D[i], P[i], i);
    }
    as1.init();
    ds1.init();
    for (auto i : as1.ps) usedA[i.se] = 1;
    for (auto i : ds1.ps) usedD[i.se] = 1;
    for (int i = 0; i < n; ++i) {
        if (!usedA[i]) as2.add(A[i], P[i], i);
        if (!usedD[i]) ds2.add(D[i], P[i], i);
    }
    as2.init();
    ds2.init();
}

llong BestSquad(int x, int y) {
    auto a1 = as1.get(x, y);
    auto a2 = as2.get(x, y);
    for (auto i : a2) a1.push_back(i);
    auto d1 = ds1.get(x, y);
    auto d2 = ds2.get(x, y);
    for (auto i : d2) d1.push_back(i);
    llong ans = 0;
    for (auto i : a1) for (auto j : d1) {
        if (i.se == j.se) continue;
        llong A = i.fs.fs * x + i.fs.se * y;
        llong D = j.fs.fs * x + j.fs.se * y;
        ans = max(ans, A + D);
    }
    return ans;
}

Compilation message

squad.cpp: In member function 'std::vector<std::pair<std::pair<long long int, long long int>, int> > convex_hull::get(llong, llong)':
squad.cpp:52:53: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = max(0, s - 1); i <= e + 1 && i < ps.size(); ++i) ret.push_back(ps[i]);
                                                   ~~^~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 352 ms 49128 KB Output is correct
4 Correct 352 ms 54244 KB Output is correct
5 Correct 21 ms 3036 KB Output is correct
6 Correct 283 ms 40900 KB Output is correct
7 Correct 270 ms 40900 KB Output is correct
8 Correct 287 ms 40900 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 12 ms 896 KB Output is correct
3 Correct 689 ms 51368 KB Output is correct
4 Correct 672 ms 51368 KB Output is correct
5 Correct 32 ms 2204 KB Output is correct
6 Correct 717 ms 44288 KB Output is correct
7 Correct 723 ms 44240 KB Output is correct
8 Correct 693 ms 44208 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 352 ms 49128 KB Output is correct
4 Correct 352 ms 54244 KB Output is correct
5 Correct 21 ms 3036 KB Output is correct
6 Correct 283 ms 40900 KB Output is correct
7 Correct 270 ms 40900 KB Output is correct
8 Correct 287 ms 40900 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 12 ms 896 KB Output is correct
11 Correct 689 ms 51368 KB Output is correct
12 Correct 672 ms 51368 KB Output is correct
13 Correct 32 ms 2204 KB Output is correct
14 Correct 717 ms 44288 KB Output is correct
15 Correct 723 ms 44240 KB Output is correct
16 Correct 693 ms 44208 KB Output is correct
17 Correct 113 ms 2808 KB Output is correct
18 Correct 14 ms 896 KB Output is correct
19 Correct 888 ms 54504 KB Output is correct
20 Correct 909 ms 54568 KB Output is correct
21 Correct 37 ms 2056 KB Output is correct
22 Correct 932 ms 40900 KB Output is correct
23 Correct 937 ms 40900 KB Output is correct
24 Correct 899 ms 40900 KB Output is correct