oj.uz

답안 #149988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149988 2019-09-01T07:30:14 Z ummm(#3574, cerberus, aayush9, knandy) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 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);
void merge(ConvexHullTrick &c, ConvexHullTrick &l, ConvexHullTrick &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) {
		dtree[i].add(-player[l].p, -player[l].d, l);
		atree[i].add(-player[l].p, -player[l].a, l);
	} else {
		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);
		// }
		merge(atree[i], atree[lc], atree[rc]);
		merge(dtree[i], dtree[lc], dtree[rc]);
	}
}

void merge(ConvexHullTrick &c, ConvexHullTrick &l, ConvexHullTrick &r) {
	c = l;
	int sz = r.M.size();
	for (int i = 0; i < sz; ++i) {
		c.add(r.M[i], r.B[i], r.ids[i]);
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 225812 KB Output is correct
2 Correct 130 ms 226424 KB Output is correct
3 Correct 945 ms 396536 KB Output is correct
4 Correct 936 ms 396536 KB Output is correct
5 Correct 200 ms 245624 KB Output is correct
6 Correct 1630 ms 524288 KB Output is correct
7 Correct 1826 ms 524288 KB Output is correct
8 Correct 1604 ms 524288 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 225784 KB Output is correct
2 Correct 146 ms 227576 KB Output is correct
3 Correct 1427 ms 489628 KB Output is correct
4 Correct 1314 ms 492536 KB Output is correct
5 Correct 179 ms 238072 KB Output is correct
6 Correct 2133 ms 524288 KB Output is correct
7 Correct 2027 ms 524288 KB Output is correct
8 Correct 2031 ms 524288 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 225812 KB Output is correct
2 Correct 130 ms 226424 KB Output is correct
3 Correct 945 ms 396536 KB Output is correct
4 Correct 936 ms 396536 KB Output is correct
5 Correct 200 ms 245624 KB Output is correct
6 Correct 1630 ms 524288 KB Output is correct
7 Correct 1826 ms 524288 KB Output is correct
8 Correct 1604 ms 524288 KB Output is correct
9 Correct 125 ms 225784 KB Output is correct
10 Correct 146 ms 227576 KB Output is correct
11 Correct 1427 ms 489628 KB Output is correct
12 Correct 1314 ms 492536 KB Output is correct
13 Correct 179 ms 238072 KB Output is correct
14 Correct 2133 ms 524288 KB Output is correct
15 Correct 2027 ms 524288 KB Output is correct
16 Correct 2031 ms 524288 KB Output is correct
17 Correct 219 ms 228344 KB Output is correct
18 Correct 134 ms 227576 KB Output is correct
19 Correct 1163 ms 398900 KB Output is correct
20 Correct 1162 ms 398904 KB Output is correct
21 Correct 225 ms 238968 KB Output is correct
22 Execution timed out 3082 ms 524288 KB Time limit exceeded
23 Halted 0 ms 0 KB -