This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../../src/template/template.hpp"
#include "../../../src/random/permuted_congruential_generator.hpp"
#include "../../../src/data_structure/convex_hull_trick.hpp"
void test_random() {
const int n = rng(1, 200);
vector<pair<ll, ll>> lines;
ConvexHullTrick<ll> cht;
ll a = rng(-1000, 1000);
rep(i, 0, n) {
a -= rng(0, 5);
const ll b = rng(-1000000, 1000000);
lines.emplace_back(a, b);
cht.add(a, b);
}
ll x = rng(-1000, 1000);
const int query_num = 200;
rep(_, 0, query_num) {
x += rng(0, 10);
ll expected = inf;
for(const auto& [a, b] : lines) {
expected = min(expected, a * x + b);
}
assert(cht(x) == expected);
}
}
void test_sample_like() {
ConvexHullTrick<ll> cht;
vector<pair<ll, ll>> lines{{5, 3}, {2, 10}, {-1, 20}, {-4, 100}};
for(const auto& [a, b] : lines) cht.add(a, b);
rep(x, -10, 31) {
ll expected = inf;
for(const auto& [a, b] : lines) {
expected = min(expected, a * x + b);
}
assert(cht(x) == expected);
}
}
int main(void) {
test_sample_like();
constexpr int test_num = 100;
rep(_, 0, test_num) {
test_random();
}
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}#line 1 "verify/unit_test/data_structure/convex_hull_trick.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
#line 4 "src/template/template.hpp"
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
SetupIO() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(30);
}
} setup_io;
#line 3 "src/random/permuted_congruential_generator.hpp"
struct PermutedCongruentialGenerator {
template <typename T>
requires(is_integral_v<T> and sizeof(T) == 4) or (is_floating_point_v<T> and sizeof(T) == 8)
inline T operator()(const T l, const T r) {
assert(l <= r);
if constexpr(is_integral_v<T>) {
const unsigned int x = next32();
if constexpr(is_signed_v<T>) {
const uint64_t range = uint64_t(int64_t(r) - int64_t(l)) + 1;
const uint64_t offset = range == (uint64_t(1) << 32) ? x : x % range;
return T(int64_t(l) + int64_t(offset));
} else {
const uint64_t range = uint64_t(r) - uint64_t(l) + 1;
const uint64_t offset = range == (uint64_t(1) << 32) ? x : x % range;
return T(l + T(offset));
}
} else {
static constexpr unsigned long long denom = 1ull << 53;
const unsigned long long x = next64() >> 11;
const double u = static_cast<double>(x) / denom;
return l + (r - l) * u;
}
}
private:
static constexpr unsigned long long MULT = 6364136223846793005;
static inline unsigned long long state = chrono::steady_clock::now().time_since_epoch().count();
inline unsigned int next32() {
unsigned long long x = state;
state *= MULT;
const unsigned int count = x >> 61;
x ^= x >> 22;
return static_cast<unsigned int>(x >> (22 + count));
}
inline unsigned long long next64() {
return (static_cast<unsigned long long>(next32()) << 32) | next32();
}
} rng;
#line 3 "src/data_structure/convex_hull_trick.hpp"
template <typename T>
struct ConvexHullTrick {
void add(const T& a, const T& b) {
Linear l(a, b);
assert(ls.empty() or ls.back().a >= l.a);
if(!ls.empty() and ls.back().a == l.a) {
if(ls.back().b <= l.b) return;
ls.pop_back();
}
int len = (int)ls.size();
while(len >= 2 and check(ls[len - 2], ls[len - 1], l)) {
--len;
ls.pop_back();
}
ls.emplace_back(l);
}
T operator()(const T& x) {
assert(x >= x_last);
while((int)ls.size() >= 2 and ls[0](x) >= ls[1](x)) {
ls.pop_front();
}
x_last = x;
return ls[0](x);
}
private:
struct Linear {
T a, b;
Linear(const T& a = 0, const T& b = 0)
: a(a), b(b) {}
inline T operator()(const T& x) const {
return a * x + b;
}
};
inline bool check(const Linear& f1, const Linear& f2, const Linear& f3) const {
return (f2.a - f1.a) * (f3.b - f2.b) >= (f2.b - f1.b) * (f3.a - f2.a);
}
deque<Linear> ls;
T x_last = numeric_limits<T>::min();
};
#line 5 "verify/unit_test/data_structure/convex_hull_trick.test.cpp"
void test_random() {
const int n = rng(1, 200);
vector<pair<ll, ll>> lines;
ConvexHullTrick<ll> cht;
ll a = rng(-1000, 1000);
rep(i, 0, n) {
a -= rng(0, 5);
const ll b = rng(-1000000, 1000000);
lines.emplace_back(a, b);
cht.add(a, b);
}
ll x = rng(-1000, 1000);
const int query_num = 200;
rep(_, 0, query_num) {
x += rng(0, 10);
ll expected = inf;
for(const auto& [a, b] : lines) {
expected = min(expected, a * x + b);
}
assert(cht(x) == expected);
}
}
void test_sample_like() {
ConvexHullTrick<ll> cht;
vector<pair<ll, ll>> lines{{5, 3}, {2, 10}, {-1, 20}, {-4, 100}};
for(const auto& [a, b] : lines) cht.add(a, b);
rep(x, -10, 31) {
ll expected = inf;
for(const auto& [a, b] : lines) {
expected = min(expected, a * x + b);
}
assert(cht(x) == expected);
}
}
int main(void) {
test_sample_like();
constexpr int test_num = 100;
rep(_, 0, test_num) {
test_random();
}
int a, b;
cin >> a >> b;
cout << a + b << '\n';
}