Submission #150003

#	Time	Username	Problem	Language	Result	Execution time	Memory
150003		rkm0959 (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	1122 ms	37708 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

using lint = long long;

struct Data {
    Data() {}
    Data(lint x, lint y, lint i) : x(x), y(y), i(i) {}

    lint x, y, i;
    lint f(lint a, lint b) { return a*x + b*y; }
    bool operator<(const Data b) const { return x < b.x or (x == b.x and y > b.y); }
};

int ccw(Data a, Data b, Data c) {
    lint k = a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
    if (k>0) return 1;
    if (k<0) return -1;
    return 0;
}

struct cht {
    vector<Data> v;
    void add(Data p) {
        while (v.size() >= 2 and ccw(v[v.size()-2], v[v.size()-1], p) >= 0) v.pop_back();
        v.push_back(p);
    }

    Data find(lint a, lint b) {
        if (v.empty()) return Data(0, 0, 0);
        int l = -1, r = v.size()-1;
        while (l+1<r) {
            int m = (l+r) / 2;
            if (b * (v[m+1].y - v[m].y) >= - a * (v[m+1].x - v[m].x)) l = m;
            else r = m;
        }
        return v[r];
    }

    lint second(lint a, lint b) {
        int l = -1, r = v.size()-1;
        while (l+1<r) {
            int m = (l+r) / 2;
            if (b * (v[m+1].y - v[m].y) >= - a * (v[m+1].x - v[m].x)) l = m;
            else r = m;
        }
        lint ans = -1e18;
        if (r > 0) ans = max(ans, v[r-1].f(a, b));
        if (r < v.size()-1) ans = max(ans, v[r+1].f(a, b));
        return ans;
    }
} a1, a2, d1, d2;

int n;
struct human {
    int a, d, p, i;
} a[300004];

void Init(vector<int> A, vector<int> D, vector<int> P){
    n = A.size();
    for (int i=0; i<n; i++) a[i] = (human) { A[i], D[i], P[i], i };

    sort(a, a+n, [](human x, human y) { return x.a < y.a or (x.a == y.a and x.p > y.p); });
    
    for (int i=0; i<n; i++) a1.add(Data(a[i].a, a[i].p, a[i].i));
    for (int i=0; i<n; i++) if (!binary_search(a1.v.begin(), a1.v.end(), Data(a[i].a, a[i].p, a[i].i))) a2.add(Data(a[i].a, a[i].p, a[i].i));
    
    sort(a, a+n, [](human x, human y) { return x.d < y.d or (x.d == y.d and x.p > y.p); });
    
    for (int i=0; i<n; i++) d1.add(Data(a[i].d, a[i].p, a[i].i));
    for (int i=0; i<n; i++) if (!binary_search(d1.v.begin(), d1.v.end(), Data(a[i].d, a[i].p, a[i].i))) d2.add(Data(a[i].d, a[i].p, a[i].i));
}

long long BestSquad(int X, int Y){
    Data a = a1.find(X, Y), d = d1.find(X, Y);
    if (a.i != d.i) {
        return a.f(X, Y) + d.f(X, Y);
    } else {
        lint aa = max(a1.second(X, Y), a2.find(X, Y).f(X, Y)), dd = max(d1.second(X, Y), d2.find(X, Y).f(X, Y));
        return max(a.f(X, Y) + dd, d.f(X, Y) + aa);
    }
}

Compilation message (stderr)

squad.cpp: In member function 'lint cht::second(lint, lint)':
squad.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (r < v.size()-1) ans = max(ans, v[r+1].f(a, b));
             ~~^~~~~~~~~~~~

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