Contest Duration: ~ (local time) (240 minutes)

Submission #8265493

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }

namespace convex_hull_trick_details {
/**
* @note y = ax + b
*/
struct line_t { int64_t a, b; };
bool operator < (line_t lhs, line_t rhs) {
return std::make_pair(- lhs.a, lhs.b) < std::make_pair(- rhs.a, rhs.b);
}

struct rational_t { int64_t num, den; };
bool operator < (rational_t lhs, rational_t rhs) {
if (lhs.num ==   INT64_MAX or rhs.num == - INT64_MAX) return false;
if (lhs.num == - INT64_MAX or rhs.num ==   INT64_MAX) return true;
return lhs.num * rhs.den < rhs.num * lhs.den;  // TODO: check overflow
}
}

class convex_hull_trick {
typedef convex_hull_trick_details::line_t line_t;
typedef convex_hull_trick_details::rational_t rational_t;
static rational_t make_rational(int64_t num, int64_t den = 1) {
if (den < 0) { num *= -1; den *= -1; }
return { num, den };  // NOTE: no reduction
}

public:
convex_hull_trick() {
lines.insert({ + INT64_MAX, 0 });  // sentinels
lines.insert({ - INT64_MAX, 0 });
cross.emplace(make_rational(- INT64_MAX), (line_t) { - INT64_MAX, 0 });
}
/**
* @note O(log n)
*/
void add_line(int64_t a, int64_t b) {
auto it = lines.insert({ a, b }).first;
if (not is_required(*prev(it), { a, b }, *next(it))) {
lines.erase(it);
return;
}
cross.erase(cross_point(*prev(it), *next(it)));
{  // remove right lines
auto ju = prev(it);
while (ju != lines.begin() and not is_required(*prev(ju), *ju, { a, b })) -- ju;
cross_erase(ju, prev(it));
it = lines.erase(++ ju, it);
}
{  // remove left lines
auto ju = next(it);
while(next(ju) != lines.end() and not is_required({ a, b }, *ju, *next(ju))) ++ ju;
cross_erase(++ it, ju);
it = prev(lines.erase(it, ju));
}
cross.emplace(cross_point(*prev(it), *it), *it);
cross.emplace(cross_point(*it, *next(it)), *next(it));
assert (not empty());
}
bool empty() const {
return lines.size() <= 2;
}
/**
* @note O(log n)
*/
int64_t get_min(int64_t x) const {
assert (not empty());
line_t f = prev(cross.lower_bound(make_rational(x)))->second;
return f.a * x + f.b;
}

private:
std::set<line_t> lines;
std::map<rational_t, line_t> cross;
template <typename Iterator>
void cross_erase(Iterator first, Iterator last) {
for (; first != last; ++ first) {
cross.erase(cross_point(*first, *next(first)));
}
}
rational_t cross_point(line_t f1, line_t f2) const {
if (f1.a ==   INT64_MAX) return make_rational(- INT64_MAX);
if (f2.a == - INT64_MAX) return make_rational(  INT64_MAX);
return make_rational(f1.b - f2.b, f2.a - f1.a);
}
bool is_required(line_t f1, line_t f2, line_t f3) const {
if (f1.a == f2.a and f1.b <= f2.b) return false;
if (f1.a == INT64_MAX or f3.a == - INT64_MAX) return true;
return (f2.a - f1.a) * (f3.b - f2.b) < (f2.b - f1.b) * (f3.a - f2.a);
}
};

struct shop_t {
int open;
int close;
int64_t d;
int64_t x;
};

vector<int64_t> solve(int n, const vector<shop_t> & shops) {
int t_max = 0;
for (auto shop : shops) {
chmax(t_max, shop.open + 3);
chmax(t_max, shop.close + 3);
}

// CHTs on a segment tree
int k = 0;
while ((1 << k) < t_max) {
++ k;
}
vector<convex_hull_trick> segtree(2 * (1 << k) - 1);
auto range_update = [&](int l, int r, int64_t a, int64_t b) {
assert (0 <= l and l < r and r <= (1 << k));
function<void (int)> go = [&](int i) {
assert (0 <= i and i < 2 * (1 << k));
int d = 32 - __builtin_clz(i + 1) - 1;
int j = i - (1 << d) + 1;
int il = (1 << (k - d)) * j;
int ir = (1 << (k - d)) * (j + 1);
if (ir <= l or r <= il) {
// nop
} else if (l <= il and ir <= r) {
} else {
go(2 * i + 1);
go(2 * i + 2);
}
};
go(0);
};
auto point_get = [&](int i, int64_t x) {
assert (0 <= i and i < (1 << k));
int64_t y = INT64_MAX;
i += (1 << k) - 1;
while (true) {
if (not segtree[i].empty()) {
chmin(y, segtree[i].get_min(x));
}
if (i == 0) break;
i = (i - 1) / 2;
}
return y;
};

// run
vector<int64_t> p(n);
REP (i, n) {
auto shop = shops[i];
int64_t y = point_get(shop.open, shop.d);
p[i] = min(shop.x, y == INT64_MAX ? INT64_MAX : shop.d * shop.d + y);
int64_t a = - 2 * shop.d;
int64_t b = p[i] + shop.d * shop.d;
range_update(shop.open + 1, shop.close != -1 ? shop.close + 2 : t_max, a, b);
}
return p;
}

int main() {
int n; cin >> n;
vector<shop_t> shops(n);
REP (i, n) {
cin >> shops[i].open;
cin >> shops[i].close;
cin >> shops[i].d;
cin >> shops[i].x;
}
vector<int64_t> prices = solve(n, shops);
REP (i, n) {
cout << prices[i] << endl;
}
return 0;
}
```

#### Submission Info

Submission Time 2019-11-03 12:52:27+0900 I - Ramen kimiyuki C++14 (GCC 5.4.1) 300 5886 Byte AC 2306 ms 224640 KB

#### Judge Result

Set Name Score / Max Score Test Cases
All 300 / 300 0-sample-1, 0-sample-2, 1-random-0, 1-random-1, 1-random-2, 1-random-3, 1-random-4, 2-0, 2-1, 3-0, 3-1, 4-1, 4-2, 5-0, 5-1, 6-0, 6-1, 6-2, 7-1
Case Name Status Exec Time Memory
0-sample-1 1 ms 256 KB
0-sample-2 1 ms 256 KB
1-random-0 39 ms 4864 KB
1-random-1 53 ms 6528 KB
1-random-2 51 ms 6144 KB
1-random-3 1118 ms 157568 KB
1-random-4 2306 ms 224640 KB
2-0 1760 ms 167168 KB
2-1 1795 ms 170112 KB
3-0 1503 ms 159232 KB
3-1 1606 ms 160128 KB
4-1 871 ms 111360 KB
4-2 850 ms 111232 KB
5-0 2062 ms 107776 KB
5-1 2095 ms 107392 KB
6-0 363 ms 42240 KB
6-1 381 ms 43648 KB
6-2 411 ms 46592 KB
7-1 425 ms 95232 KB