oj.uz

답안 #150818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150818 2019-09-01T08:57:45 Z ummm(#3574, cerberus, aayush9, knandy) 최적의 팀 구성 (FXCUP4_squad) C++17
47 / 100
 3000 ms 499516 KB 
/* cerberus97 - Hanit Banga */

#pragma comment(linker, "stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#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);
pll query2(ConvexHullTrick* tree, int i, int l, int r, int avoid, int x, int y, bool skip = false);

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 = query2(atree, 1, 1, n, -1, x, y);
	auto bd = query2(dtree, 1, 1, n, -1, 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));
	auto td = query2(dtree, 1, 1, n, ba.second, x, y);
	auto ta = query2(atree, 1, 1, n, bd.second, 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;
// 		}
// 	}
// }

pll query2(ConvexHullTrick* tree, int i, int l, int r, int avoid, int x, int y, bool skip) {
	if (l == r and l == avoid) {
		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 (avoid < l or avoid > r) {
			return tree[i].query(x, y);
		} else if (!skip) {
			auto cur = tree[i].query(x, y);
			if (cur.second != avoid) {
				return cur;
			}
		}
		int mid = (l + r) / 2, lc = 2 * i, rc = lc + 1;
		auto a1 = query2(tree, lc, l, mid, avoid, x, y, true);
		auto a2 = query2(tree, rc, mid + 1, r, avoid, x, y, true);
		if (a1.first > a2.first) {
			return a1;
		} else {
			return a2;
		}
	}
}

Compilation message

squad.cpp:3:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "stack:200000000")

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 225784 KB Output is correct
2 Correct 149 ms 226168 KB Output is correct
3 Correct 987 ms 323320 KB Output is correct
4 Correct 996 ms 323320 KB Output is correct
5 Correct 204 ms 240632 KB Output is correct
6 Correct 1418 ms 497344 KB Output is correct
7 Correct 1394 ms 497232 KB Output is correct
8 Correct 1328 ms 497344 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 225784 KB Output is correct
2 Correct 158 ms 226936 KB Output is correct
3 Correct 1318 ms 415392 KB Output is correct
4 Correct 1397 ms 418544 KB Output is correct
5 Correct 179 ms 235000 KB Output is correct
6 Correct 1433 ms 499516 KB Output is correct
7 Correct 1605 ms 499460 KB Output is correct
8 Correct 1650 ms 499456 KB Output is correct

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 225784 KB Output is correct
2 Correct 149 ms 226168 KB Output is correct
3 Correct 987 ms 323320 KB Output is correct
4 Correct 996 ms 323320 KB Output is correct
5 Correct 204 ms 240632 KB Output is correct
6 Correct 1418 ms 497344 KB Output is correct
7 Correct 1394 ms 497232 KB Output is correct
8 Correct 1328 ms 497344 KB Output is correct
9 Correct 145 ms 225784 KB Output is correct
10 Correct 158 ms 226936 KB Output is correct
11 Correct 1318 ms 415392 KB Output is correct
12 Correct 1397 ms 418544 KB Output is correct
13 Correct 179 ms 235000 KB Output is correct
14 Correct 1433 ms 499516 KB Output is correct
15 Correct 1605 ms 499460 KB Output is correct
16 Correct 1650 ms 499456 KB Output is correct
17 Correct 240 ms 228344 KB Output is correct
18 Correct 151 ms 226808 KB Output is correct
19 Correct 1156 ms 325500 KB Output is correct
20 Correct 1126 ms 325684 KB Output is correct
21 Correct 259 ms 235640 KB Output is correct
22 Execution timed out 3125 ms 497344 KB Time limit exceeded
23 Halted 0 ms 0 KB -