oj.uz

Submission #149680

# Submission time Handle Problem Language Result Execution time Memory
149680 2019-09-01T06:57:11 Z ummm(#3574, cerberus, aayush9, knandy) Organizing the Best Squad (FXCUP4_squad) C++17
0 / 100
 2353 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<LL> M;
	vector<LL> 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
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 225784 KB Output is correct
2 Correct 141 ms 226168 KB Output is correct
3 Correct 1169 ms 336760 KB Output is correct
4 Correct 1182 ms 336764 KB Output is correct
5 Correct 210 ms 252132 KB Output is correct
6 Execution timed out 2353 ms 524288 KB Time limit exceeded (wall clock)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 225784 KB Output is correct
2 Correct 142 ms 227576 KB Output is correct
3 Correct 2015 ms 524288 KB Output is correct
4 Correct 1955 ms 524288 KB Output is correct
5 Correct 208 ms 239864 KB Output is correct
6 Execution timed out 1936 ms 524288 KB Time limit exceeded (wall clock)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 225784 KB Output is correct
2 Correct 141 ms 226168 KB Output is correct
3 Correct 1169 ms 336760 KB Output is correct
4 Correct 1182 ms 336764 KB Output is correct
5 Correct 210 ms 252132 KB Output is correct
6 Execution timed out 2353 ms 524288 KB Time limit exceeded (wall clock)
7 Halted 0 ms 0 KB -