oj.uz

답안 #149871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149871 2019-09-01T07:18:32 Z ummm(#3574, cerberus, aayush9, knandy) 최적의 팀 구성 (FXCUP4_squad) C++17
19 / 100
 3000 ms 499460 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);
	if (bd.second != id) {
		return ans;
	}
	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) {
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 225808 KB Output is correct
2 Correct 135 ms 226168 KB Output is correct
3 Correct 1030 ms 323452 KB Output is correct
4 Correct 983 ms 323320 KB Output is correct
5 Correct 173 ms 240632 KB Output is correct
6 Correct 1229 ms 497364 KB Output is correct
7 Correct 1056 ms 497348 KB Output is correct
8 Correct 1182 ms 497344 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 225656 KB Output is correct
2 Correct 149 ms 226960 KB Output is correct
3 Correct 1589 ms 415388 KB Output is correct
4 Correct 1675 ms 418544 KB Output is correct
5 Correct 204 ms 235000 KB Output is correct
6 Correct 2378 ms 499456 KB Output is correct
7 Correct 2405 ms 499460 KB Output is correct
8 Execution timed out 3053 ms 499456 KB Time limit exceeded

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 225808 KB Output is correct
2 Correct 135 ms 226168 KB Output is correct
3 Correct 1030 ms 323452 KB Output is correct
4 Correct 983 ms 323320 KB Output is correct
5 Correct 173 ms 240632 KB Output is correct
6 Correct 1229 ms 497364 KB Output is correct
7 Correct 1056 ms 497348 KB Output is correct
8 Correct 1182 ms 497344 KB Output is correct
9 Correct 136 ms 225656 KB Output is correct
10 Correct 149 ms 226960 KB Output is correct
11 Correct 1589 ms 415388 KB Output is correct
12 Correct 1675 ms 418544 KB Output is correct
13 Correct 204 ms 235000 KB Output is correct
14 Correct 2378 ms 499456 KB Output is correct
15 Correct 2405 ms 499460 KB Output is correct
16 Execution timed out 3053 ms 499456 KB Time limit exceeded