oj.uz

Submission #149898

# Submission time Handle Problem Language Result Execution time Memory
149898 2019-09-01T07:21:54 Z ummm(#3574, cerberus, aayush9, knandy) Organizing the Best Squad (FXCUP4_squad) C++17
47 / 100
 3000 ms 499508 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);
	auto bd = query(dtree, 1, 1, n, 1, n, x, y);
	if (ba.second != bd.second) {
		return ba.first + bd.first;
	}
	auto td = max(query(dtree, 1, 1, n, 1, ba.second - 1, x, y), query(dtree, 1, 1, n, ba.second + 1, n, x, y));
	auto ta = max(query(atree, 1, 1, n, 1, bd.second - 1, x, y), query(atree, 1, 1, n, bd.second + 1, n, x, y));
	return max(ba.first + td.first, bd.first + ta.first);
}

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

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;
		auto a1 = query(tree, lc, l, mid, ql, qr, x, y);
		auto a2 = query(tree, rc, mid + 1, r, ql, qr, x, y);
		if (a1.first > a2.first) {
			return a1;
		} else {
			return a2;
		}
	}
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 225784 KB Output is correct
2 Correct 130 ms 226208 KB Output is correct
3 Correct 1000 ms 323320 KB Output is correct
4 Correct 954 ms 323320 KB Output is correct
5 Correct 199 ms 240632 KB Output is correct
6 Correct 1190 ms 497216 KB Output is correct
7 Correct 1111 ms 497216 KB Output is correct
8 Correct 1242 ms 497344 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 225656 KB Output is correct
2 Correct 127 ms 226808 KB Output is correct
3 Correct 1368 ms 415388 KB Output is correct
4 Correct 1399 ms 418548 KB Output is correct
5 Correct 184 ms 234872 KB Output is correct
6 Correct 1524 ms 499460 KB Output is correct
7 Correct 1468 ms 499460 KB Output is correct
8 Correct 1471 ms 499508 KB Output is correct

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 225784 KB Output is correct
2 Correct 130 ms 226208 KB Output is correct
3 Correct 1000 ms 323320 KB Output is correct
4 Correct 954 ms 323320 KB Output is correct
5 Correct 199 ms 240632 KB Output is correct
6 Correct 1190 ms 497216 KB Output is correct
7 Correct 1111 ms 497216 KB Output is correct
8 Correct 1242 ms 497344 KB Output is correct
9 Correct 126 ms 225656 KB Output is correct
10 Correct 127 ms 226808 KB Output is correct
11 Correct 1368 ms 415388 KB Output is correct
12 Correct 1399 ms 418548 KB Output is correct
13 Correct 184 ms 234872 KB Output is correct
14 Correct 1524 ms 499460 KB Output is correct
15 Correct 1468 ms 499460 KB Output is correct
16 Correct 1471 ms 499508 KB Output is correct
17 Correct 212 ms 228344 KB Output is correct
18 Correct 156 ms 226808 KB Output is correct
19 Correct 1084 ms 325556 KB Output is correct
20 Correct 1069 ms 325684 KB Output is correct
21 Correct 223 ms 235640 KB Output is correct
22 Execution timed out 3122 ms 498048 KB Time limit exceeded
23 Halted 0 ms 0 KB -