oj.uz

Submission #148436

# Submission time Handle Problem Language Result Execution time Memory
148436 2019-09-01T04:23:23 Z Ian and 2-bit memory(#3648, percywtc, nhho, ulna) Organizing the Best Squad (FXCUP4_squad) C++17
19 / 100
 905 ms 76664 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) {
		Iterator z = this->emplace(k, m, 0, id);
		Iterator y = z++;
		Iterator x = y;
		while (Intersect(y, z))
			z = this->erase(z);
		if (x != this->begin() && Intersect(--x, y))
			Intersect(x, y = this->erase(y));
		while ((y = x) != this->begin() && (--x)->p >= y->p)
			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;
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);
		sd.Add(P[i], D[i], i);
	}
}

long long ans;

void check(CHTMultiset<long double>::Iterator ia, CHTMultiset<long double>::Iterator ib, long long x, long long y) {
	if (ia->id != ib->id) {
	int i = ia->id, j = ib->id;
	ans = max(ans, (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);
	check(ia, ib, X, Y);
	if (ia != sa.begin()) {
		if (ib != sd.begin())
		check(prev(ia), prev(ib), X, Y);
		check(prev(ia), ib, X, Y);
		if (next(ib) != sd.end())
		check(prev(ia), next(ib), X, Y);
	}
		if (ib != sd.begin())
		check(ia, prev(ib), X, Y);
		check(ia, ib, X, Y);
		if (next(ib) != sd.end())
		check(ia, next(ib), X, Y);
	if (next(ia) != sa.end()) {
		if (ib != sd.begin())
		check(next(ia), prev(ib), X, Y);
		check(next(ia), ib, X, Y);
		if (next(ib) != sd.end())
		check(next(ia), next(ib), X, Y);
	}
	return ans;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 241 ms 11000 KB Output is correct
4 Correct 249 ms 10872 KB Output is correct
5 Correct 37 ms 5368 KB Output is correct
6 Correct 873 ms 76664 KB Output is correct
7 Correct 905 ms 76664 KB Output is correct
8 Correct 888 ms 76664 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 241 ms 11000 KB Output is correct
4 Correct 249 ms 10872 KB Output is correct
5 Correct 37 ms 5368 KB Output is correct
6 Correct 873 ms 76664 KB Output is correct
7 Correct 905 ms 76664 KB Output is correct
8 Correct 888 ms 76664 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -