oj.uz

Submission #148533

# Submission time Handle Problem Language Result Execution time Memory
148533 2019-09-01T04:37:13 Z Ian and 2-bit memory(#3648, percywtc, nhho, ulna) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 2021 ms 78908 KB 
#include <bits/stdc++.h>

using namespace std;

#include "squad.h"

// [Convex Hull Trick (CHT)]
// https://github.com/kth-competitive-programming/kactl/blob/master/content/data-structures/LineContainer.h
// https://wcipeg.com/wiki/Convex_hull_trick
// Add lines of the form kx + m
// Query maximum values at points x

template<typename T>
struct CHTLine {
	T k, m;
	mutable T p;
	int id;
	CHTLine(T k_, T m_, T p_, int id_) : k(k_), m(m_), p(p_), id(id_) {}
	bool operator<(const CHTLine<T>& o) const {
		return k < o.k;
	}
	bool operator<(const T& x) const {
		return p < x;
	}
};

template<typename T>
constexpr T CHTINF;

template<>
constexpr int CHTINF<int> = INT_MAX;

template<>
constexpr long long CHTINF<long long> = LLONG_MAX;

template<>
constexpr float CHTINF<float> = HUGE_VALF;

template<>
constexpr double CHTINF<double> = HUGE_VAL;

template<>
constexpr long double CHTINF<long double> = HUGE_VALL;

template<typename T>
struct CHTMultiset : multiset<CHTLine<T>, less<>> {
	// reimplemented below for integral T
	T Divide(T a, T b) {
		return a / b;
	}
	using Iterator = typename multiset<CHTLine<T>, less<>>::iterator;
	bool Intersect(Iterator x, Iterator y) {
		if (y == this->end()) {
			x->p = CHTINF<T>;
			return false;
		}
		if (x->k == y->k)
			x->p = x->m > y->m ? CHTINF<T> : -CHTINF<T>;
		else
			x->p = Divide(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void Add(T k, T m, int id, CHTMultiset<T>* ptr) {
		Iterator z = this->emplace(k, m, 0, id);
		Iterator y = z++;
		Iterator x = y;
		while (Intersect(y, z)) {
			if (ptr) {
				ptr->Add(z->k, z->m, z->id, 0);
			}
			z = this->erase(z);
		}
		if (x != this->begin() && Intersect(--x, y)) {
			if (ptr) {
				ptr->Add(y->k, y->m, y->id, 0);
			}
			Intersect(x, y = this->erase(y));
			}
		while ((y = x) != this->begin() && (--x)->p >= y->p) {
			if (ptr) {
				ptr->Add(y->k, y->m, y->id, 0);
			}
			Intersect(x, this->erase(y));
			}
	}
	Iterator Query(T x) {
		// assert(!this->empty());
		return this->lower_bound(x);
		// return l.k * x + l.m;
	}
};

#define FLOOR_DIV(a, b) ((a) / (b) - (((a) ^ (b)) < 0 && (a) % (b)))

template<>
int CHTMultiset<int>::Divide(int a, int b) {
	return FLOOR_DIV(a, b);
}

template<>
long long CHTMultiset<long long>::Divide(long long a, long long b) {
	return FLOOR_DIV(a, b);
}

#undef FLOOR_DIV

CHTMultiset<long double> sa, sd, saa, sdd;
vector<int> aa, dd, pp;

// a * x + p * y
// (a + p * y / x) * x

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	aa = A;
	dd = D;
	pp = P;
	int N = A.size();
	for (int i = 0; i < N; i++) {
		sa.Add(P[i], A[i], i, &saa);
		sd.Add(P[i], D[i], i, &sdd);
	}
	// for (auto it = sa.begin(); it != sa.end(); it++) printf("%d ", it->id);
	// puts("");
	// for (auto it = sd.begin(); it != sd.end(); it++) printf("%d ", it->id);
	// puts("");
}

long long ans;

void check(int i, int j, long long x, long long y) {
	// printf(" %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
	if (i != j) {
	ans = max(ans, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
	}
	// i = 2, j = 3;
	// printf("  %d %d %lld\n", i, j, (aa[i] + dd[j]) * x + (pp[i] + pp[j]) * y);
}

long long BestSquad(int X, int Y){
	ans = LLONG_MIN;
	long double x = (long double) Y / X;
	auto ia = sa.Query(x);
	auto ib = sd.Query(x);
	vector<int> va = {ia->id};
	if (!saa.empty())
		va.push_back(saa.Query(x)->id);
	if (ia != sa.begin()) va.push_back(prev(ia)->id);
	if (next(ia) != sa.end()) va.push_back(next(ia)->id);
	vector<int> vb = {ib->id};
	if (!sdd.empty())
		vb.push_back(sdd.Query(x)->id);
	if (ib != sd.begin()) vb.push_back(prev(ib)->id);
	if (next(ib) != sd.end()) vb.push_back(next(ib)->id);
	for (int i : va)for (int j : vb) check(i, j ,X, Y);
	return ans;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 328 ms 11000 KB Output is correct
4 Correct 343 ms 10872 KB Output is correct
5 Correct 42 ms 5420 KB Output is correct
6 Correct 848 ms 76664 KB Output is correct
7 Correct 793 ms 76664 KB Output is correct
8 Correct 836 ms 76664 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 13 ms 256 KB Output is correct
3 Correct 639 ms 13240 KB Output is correct
4 Correct 625 ms 13240 KB Output is correct
5 Correct 35 ms 2424 KB Output is correct
6 Correct 1456 ms 46008 KB Output is correct
7 Correct 1422 ms 46008 KB Output is correct
8 Correct 1790 ms 46012 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 328 ms 11000 KB Output is correct
4 Correct 343 ms 10872 KB Output is correct
5 Correct 42 ms 5420 KB Output is correct
6 Correct 848 ms 76664 KB Output is correct
7 Correct 793 ms 76664 KB Output is correct
8 Correct 836 ms 76664 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 13 ms 256 KB Output is correct
11 Correct 639 ms 13240 KB Output is correct
12 Correct 625 ms 13240 KB Output is correct
13 Correct 35 ms 2424 KB Output is correct
14 Correct 1456 ms 46008 KB Output is correct
15 Correct 1422 ms 46008 KB Output is correct
16 Correct 1790 ms 46012 KB Output is correct
17 Correct 120 ms 2960 KB Output is correct
18 Correct 13 ms 512 KB Output is correct
19 Correct 699 ms 13268 KB Output is correct
20 Correct 661 ms 13240 KB Output is correct
21 Correct 56 ms 3960 KB Output is correct
22 Correct 1763 ms 78908 KB Output is correct
23 Correct 2021 ms 78904 KB Output is correct
24 Correct 1984 ms 78908 KB Output is correct