oj.uz

Submission #149732

# Submission time Handle Problem Language Result Execution time Memory
149732 2019-09-01T07:02:46 Z ummm(#3574, cerberus, aayush9, knandy) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 3000 ms 524288 KB 
/* cerberus97 - Hanit Banga */

#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 atree[4 * N], dtree[4 * N];

void build(int i, int l, int r);
pll query(ConvexHullTrick* tree, int i, int l, int r, int ql, int qr, 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);
	build(1, 1, n);
}

ll BestSquad(int x, int y) {
	auto ba = query(atree, 1, 1, n, 1, n, x, y);
	int id = ba.second;
	auto bd = max(query(dtree, 1, 1, n, 1, id - 1, x, y), query(dtree, 1, 1, n, id + 1, n, x, y));
	ll ans = ba.first + bd.first;
	// cout << ba.second << ' ' << bd.second << endl;
	// cout << ba.first << ' ' << bd.first << endl;
	bd = query(dtree, 1, 1, n, 1, n, x, y);
	id = bd.second;
	ba = max(query(atree, 1, 1, n, 1, id - 1, x, y), query(atree, 1, 1, n, id + 1, n, x, y));
	ans = max(ans, ba.first + bd.first);
	// cout << ba.second << ' ' << bd.second << endl;
	// cout << ba.first << ' ' << bd.first << endl;
	return ans;
}

void build(int i, int l, int r) {
	if (l < r) {
		for (int j = l; j <= r; ++j) {
			dtree[i].add(-player[j].p, -player[j].d, j);
			atree[i].add(-player[j].p, -player[j].a, j);
		}
		int mid = (l + r) / 2, lc = 2 * i, rc = lc + 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
	}
}

pll query(ConvexHullTrick* tree, int i, int l, int r, int ql, int qr, int x, int y) {
	if (l > qr or ql > r) {
		return {-1, -1};
	} else if (l == r) {
		if (tree == atree) {
			return {ll(x) * player[l].a + ll(y) * player[l].p, l};
		} else {
			return {ll(x) * player[l].d + ll(y) * player[l].p, l};
		}
	} else if (ql <= l and r <= qr) {
		return tree[i].query(x, y);
	} else {
		int mid = (l + r) / 2, lc = 2 * i, rc = lc + 1;
		return max(query(tree, lc, l, mid, ql, qr, x, y),
				   query(tree, rc, mid + 1, r, ql, qr, x, y));
	}
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 225784 KB Output is correct
2 Correct 138 ms 226168 KB Output is correct
3 Correct 1223 ms 324472 KB Output is correct
4 Correct 1246 ms 324472 KB Output is correct
5 Correct 227 ms 246004 KB Output is correct
6 Correct 1957 ms 524288 KB Output is correct
7 Correct 1950 ms 524288 KB Output is correct
8 Correct 1989 ms 524288 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 225784 KB Output is correct
2 Correct 150 ms 227320 KB Output is correct
3 Correct 2184 ms 463648 KB Output is correct
4 Correct 2071 ms 463900 KB Output is correct
5 Correct 224 ms 236664 KB Output is correct
6 Execution timed out 3125 ms 524288 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 225784 KB Output is correct
2 Correct 138 ms 226168 KB Output is correct
3 Correct 1223 ms 324472 KB Output is correct
4 Correct 1246 ms 324472 KB Output is correct
5 Correct 227 ms 246004 KB Output is correct
6 Correct 1957 ms 524288 KB Output is correct
7 Correct 1950 ms 524288 KB Output is correct
8 Correct 1989 ms 524288 KB Output is correct
9 Correct 137 ms 225784 KB Output is correct
10 Correct 150 ms 227320 KB Output is correct
11 Correct 2184 ms 463648 KB Output is correct
12 Correct 2071 ms 463900 KB Output is correct
13 Correct 224 ms 236664 KB Output is correct
14 Execution timed out 3125 ms 524288 KB Time limit exceeded
15 Halted 0 ms 0 KB -