oj.uz

Submission #151081

# Submission time Handle Problem Language Result Execution time Memory
151081 2019-09-01T17:06:29 Z cerberus Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 886 ms 62056 KB 
/* 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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 360 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 276 ms 18456 KB Output is correct
4 Correct 278 ms 18388 KB Output is correct
5 Correct 19 ms 3588 KB Output is correct
6 Correct 276 ms 50016 KB Output is correct
7 Correct 276 ms 49992 KB Output is correct
8 Correct 276 ms 49928 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 482 ms 35492 KB Output is correct
4 Correct 474 ms 35660 KB Output is correct
5 Correct 23 ms 2584 KB Output is correct
6 Correct 666 ms 50020 KB Output is correct
7 Correct 660 ms 49960 KB Output is correct
8 Correct 661 ms 50032 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 360 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 276 ms 18456 KB Output is correct
4 Correct 278 ms 18388 KB Output is correct
5 Correct 19 ms 3588 KB Output is correct
6 Correct 276 ms 50016 KB Output is correct
7 Correct 276 ms 49992 KB Output is correct
8 Correct 276 ms 49928 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 6 ms 888 KB Output is correct
11 Correct 482 ms 35492 KB Output is correct
12 Correct 474 ms 35660 KB Output is correct
13 Correct 23 ms 2584 KB Output is correct
14 Correct 666 ms 50020 KB Output is correct
15 Correct 660 ms 49960 KB Output is correct
16 Correct 661 ms 50032 KB Output is correct
17 Correct 81 ms 3088 KB Output is correct
18 Correct 7 ms 636 KB Output is correct
19 Correct 474 ms 18420 KB Output is correct
20 Correct 479 ms 18388 KB Output is correct
21 Correct 36 ms 2704 KB Output is correct
22 Correct 879 ms 49908 KB Output is correct
23 Correct 886 ms 62056 KB Output is correct
24 Correct 872 ms 61936 KB Output is correct