Submission #151081

#	Time	Username	Problem	Language	Result	Execution time	Memory
151081		cerberus	Organizing the Best Squad (FXCUP4_squad)	C++17	100 / 100	886 ms	62056 KiB

squad

/* cerberus97 - Hanit Banga */

// #pragma comment(linker, "stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include "squad.h"
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 3e5 + 10;

// Attribution - t3nsor codebook
struct ConvexHullTrick {
	typedef long long LL;
	vector<int> M;
	vector<int> B;
	vector<int> ids;
	vector<double> left;
	ConvexHullTrick() {}
	bool bad(LL m1, LL b1, LL m2, LL b2, LL m3, LL b3) {
			// Careful, this may overflow
			return (b3-b1)*(m1-m2) < (b2-b1)*(m1-m3);
	}
	// Add a new line to the structure, y = mx + b.
	// Lines must be added in decreasing order of slope.
	void add(LL m, LL b, int id) {
			while (M.size() >= 2 && bad(M[M.size()-2], B[B.size()-2], M.back(), B.back(), m, b)) {
					M.pop_back(); B.pop_back(); ids.pop_back(); left.pop_back();
			}
			if (M.size() && M.back() == m) {
					if (B.back() > b) {
							M.pop_back(); B.pop_back(); ids.pop_back(); left.pop_back();
					} else {
							return;
					}
			}
			if (M.size() == 0) {
					left.push_back(-numeric_limits<double>::infinity());
			} else {
					left.push_back((double)(b - B.back())/(M.back() - m));
			}
			M.push_back(m);
			B.push_back(b);
			ids.push_back(id);
	}
	// Get the minimum value of mx + b among all lines in the structure.
	// There must be at least one line.
    pll query(LL x, LL y) {
            int i = upper_bound(left.begin(), left.end(), double(y) / x) - left.begin();
            return {-(M[i-1]*y + B[i-1]*x), ids[i - 1]};
    }
};

struct player_t {
	int a, d, p;
	bool operator<(const player_t &o) const {
		return p < o.p;
	}
};

int n;
player_t player[N];
ConvexHullTrick cht_atk[3], cht_def[3];

void build(int n, vector<pii> vals, ConvexHullTrick cht[3]);
ll BestSquad(int x, int y);

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n = A.size();
	for (int i = 1; i <= n; ++i) {
		player[i] = {A[i - 1], D[i - 1], P[i - 1]};
	}
	sort(player + 1, player + n + 1);
	vector<pii> def_vals, atk_vals;
	for (int i = 1; i <= n; ++i) {
		def_vals.pb({player[i].d, player[i].p});
		atk_vals.pb({player[i].a, player[i].p});
	}
	build(n, def_vals, cht_def);
	build(n, atk_vals, cht_atk);
}

void build(int n, vector<pii> vals, ConvexHullTrick cht[3]) {
	for (int i = 0; i < n; ++i) {
		cht[2].add(-vals[i].second, -vals[i].first, i);
	}
	vector<vector<bool>> at(2, vector<bool>(n, false));
	int sz = cht[2].ids.size();
	for (int j = 0; j < sz; ++j) {
		at[j % 2][cht[2].ids[j]] = true;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			if (!at[j][i]) {
				cht[j].add(-vals[i].second, -vals[i].first, i);
			}
		}
	}
}

ll BestSquad(int x, int y) {
	// auto ba = cht_atk.query(x, y);
	// auto bd = cht_def.query(x, y);
	// if (ba.second != bd.second) {
	// 	return ba.first + bd.first;
	// }
	// auto sa = 
	// auto sd = 
	// return max(ba.first + td.first, bd.first + ta.first);
	ll best = 0;
	for (int ja = 0; ja < 2; ++ja) {
		auto qa = cht_atk[ja].query(x, y);
		for (int jd = 0; jd < 2; ++jd) {
			auto qd = cht_def[jd].query(x, y);
			if (qa.second != qd.second) {
				best = max(best, qa.first + qd.first);
			}
		}
	}
	return best;
}

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