This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <optional>
#include <random>
#include <vector>
#include "datastructure/slope_trick.hpp"
constexpr int B = 400;
constexpr int W = 50;
struct brute {
std::vector<long long> f;
brute() : f(2 * B + 1, 0) {}
long long& at(long long x) { return f[x + B]; }
long long at(long long x) const { return f[x + B]; }
void add(long long a) {
for (long long& v : f) v += a;
}
void add_x_minus_a(long long a) {
for (int x = -B; x <= B; x++) at(x) += std::max<long long>(0, x - a);
}
void add_a_minus_x(long long a) {
for (int x = -B; x <= B; x++) at(x) += std::max<long long>(0, a - x);
}
void prefix_min() {
for (int x = -B + 1; x <= B; x++) at(x) = std::min(at(x), at(x - 1));
}
void suffix_min() {
for (int x = B - 1; x >= -B; x--) at(x) = std::min(at(x), at(x + 1));
}
void shift(long long a, long long b) {
std::vector<long long> g(2 * B + 1);
for (int x = -B; x <= B; x++) {
long long best = at(std::clamp<long long>(x - a, -B, B));
for (long long y = std::max<long long>(-B, x - b); y <= std::min<long long>(B, x - a); y++)
best = std::min(best, at(y));
g[x + B] = best;
}
f = g;
}
long long min() const { return *std::min_element(f.begin(), f.end()); }
std::pair<std::optional<long long>, std::optional<long long>> argmin() const {
long long m = min();
int l = -B, r = B;
while (at(l) != m) l++;
while (at(r) != m) r--;
std::optional<long long> ol, orr;
if (l != -B) ol = l;
if (r != B) orr = r;
return {ol, orr};
}
};
void random_ops(std::mt19937& rng, slope_trick<long long>& st, brute& br, int ops, long long& shifted) {
for (int t = 0; t < ops; t++) {
int c = rng() % 7;
long long a = (long long)(rng() % 21) - 10;
if (c == 0) {
st.add(a);
br.add(a);
} else if (c == 1) {
st.add_x_minus_a(a);
br.add_x_minus_a(a);
} else if (c == 2) {
st.add_a_minus_x(a);
br.add_a_minus_x(a);
} else if (c == 3) {
st.add_abs(a);
br.add_x_minus_a(a);
br.add_a_minus_x(a);
} else if (c == 4) {
st.prefix_min();
br.prefix_min();
} else if (c == 5) {
st.suffix_min();
br.suffix_min();
} else {
long long b = (long long)(rng() % 11) - 5;
long long d = rng() % 6;
if (rng() % 2) {
st.shift(b);
br.shift(b, b);
shifted += std::abs(b);
} else {
st.shift(b, b + d);
br.shift(b, b + d);
shifted += std::abs(b) + d;
}
}
}
}
void check(const slope_trick<long long>& st, const brute& br, long long shifted) {
assert(shifted < B - W);
assert(st.min() == br.min());
assert(st.argmin() == br.argmin());
for (int x = -W; x <= W; x++) assert(st(x) == br.at(x));
}
int main() {
std::mt19937 rng(20261030);
for (int it = 0; it < 3000; it++) {
slope_trick<long long> st;
brute br;
long long shifted = 0;
int ops = rng() % 25;
for (int t = 0; t < ops; t++) {
random_ops(rng, st, br, 1, shifted);
check(st, br, shifted);
}
}
for (int it = 0; it < 2000; it++) {
slope_trick<long long> f, g;
brute bf, bg;
long long shifted = 0;
random_ops(rng, f, bf, rng() % 12, shifted);
random_ops(rng, g, bg, rng() % 12, shifted);
f.merge(g);
for (int x = -B; x <= B; x++) bf.at(x) += bg.at(x);
check(f, bf, shifted);
assert(g.min() == 0);
assert(!g.argmin().first && !g.argmin().second);
assert(g(7) == 0);
}
{
slope_trick<long long> f;
assert(f.min() == 0);
assert(!f.argmin().first && !f.argmin().second);
f.add_x_minus_a(3);
assert(f.argmin() == std::make_pair(std::optional<long long>(), std::optional<long long>(3)));
f.add_a_minus_x(-2);
assert(f.argmin() == std::make_pair(std::optional<long long>(-2), std::optional<long long>(3)));
f.add_abs(10);
assert(f.min() == 7);
assert(f.argmin() == std::make_pair(std::optional<long long>(3), std::optional<long long>(10)));
}
std::cout << "Hello World" << std::endl;
}#line 1 "test/unit/slope_trick.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <optional>
#include <random>
#include <vector>
#line 4 "datastructure/slope_trick.hpp"
#include <functional>
#line 6 "datastructure/slope_trick.hpp"
#include <utility>
#line 8 "datastructure/slope_trick.hpp"
template <class T> struct slope_trick {
slope_trick() : min_f(0), add_l(0), add_r(0) {}
T min() const { return min_f; }
std::pair<std::optional<T>, std::optional<T>> argmin() const {
std::optional<T> l, r;
if (!L.empty()) l = L.front() + add_l;
if (!R.empty()) r = R.front() + add_r;
return {l, r};
}
void add(T a) { min_f += a; }
void add_x_minus_a(T a) {
if (!L.empty()) min_f += std::max<T>(0, L.front() + add_l - a);
push_l(a);
push_r(pop_l());
}
void add_a_minus_x(T a) {
if (!R.empty()) min_f += std::max<T>(0, a - (R.front() + add_r));
push_r(a);
push_l(pop_r());
}
void add_abs(T a) {
add_x_minus_a(a);
add_a_minus_x(a);
}
void prefix_min() {
R.clear();
add_r = 0;
}
void suffix_min() {
L.clear();
add_l = 0;
}
void shift(T a) { shift(a, a); }
void shift(T a, T b) {
assert(a <= b);
add_l += a;
add_r += b;
}
void merge(slope_trick& g) {
if (L.size() + R.size() < g.L.size() + g.R.size()) std::swap(*this, g);
min_f += g.min_f;
for (T l : g.L) add_a_minus_x(l + g.add_l);
for (T r : g.R) add_x_minus_a(r + g.add_r);
g = slope_trick();
}
T operator()(T x) const {
T res = min_f;
for (T l : L) res += std::max<T>(0, l + add_l - x);
for (T r : R) res += std::max<T>(0, x - (r + add_r));
return res;
}
private:
T min_f, add_l, add_r;
std::vector<T> L, R;
void push_l(T a) {
L.push_back(a - add_l);
std::push_heap(L.begin(), L.end());
}
void push_r(T a) {
R.push_back(a - add_r);
std::push_heap(R.begin(), R.end(), std::greater<T>());
}
T pop_l() {
std::pop_heap(L.begin(), L.end());
T a = L.back() + add_l;
L.pop_back();
return a;
}
T pop_r() {
std::pop_heap(R.begin(), R.end(), std::greater<T>());
T a = R.back() + add_r;
R.pop_back();
return a;
}
};
#line 10 "test/unit/slope_trick.test.cpp"
constexpr int B = 400;
constexpr int W = 50;
struct brute {
std::vector<long long> f;
brute() : f(2 * B + 1, 0) {}
long long& at(long long x) { return f[x + B]; }
long long at(long long x) const { return f[x + B]; }
void add(long long a) {
for (long long& v : f) v += a;
}
void add_x_minus_a(long long a) {
for (int x = -B; x <= B; x++) at(x) += std::max<long long>(0, x - a);
}
void add_a_minus_x(long long a) {
for (int x = -B; x <= B; x++) at(x) += std::max<long long>(0, a - x);
}
void prefix_min() {
for (int x = -B + 1; x <= B; x++) at(x) = std::min(at(x), at(x - 1));
}
void suffix_min() {
for (int x = B - 1; x >= -B; x--) at(x) = std::min(at(x), at(x + 1));
}
void shift(long long a, long long b) {
std::vector<long long> g(2 * B + 1);
for (int x = -B; x <= B; x++) {
long long best = at(std::clamp<long long>(x - a, -B, B));
for (long long y = std::max<long long>(-B, x - b); y <= std::min<long long>(B, x - a); y++)
best = std::min(best, at(y));
g[x + B] = best;
}
f = g;
}
long long min() const { return *std::min_element(f.begin(), f.end()); }
std::pair<std::optional<long long>, std::optional<long long>> argmin() const {
long long m = min();
int l = -B, r = B;
while (at(l) != m) l++;
while (at(r) != m) r--;
std::optional<long long> ol, orr;
if (l != -B) ol = l;
if (r != B) orr = r;
return {ol, orr};
}
};
void random_ops(std::mt19937& rng, slope_trick<long long>& st, brute& br, int ops, long long& shifted) {
for (int t = 0; t < ops; t++) {
int c = rng() % 7;
long long a = (long long)(rng() % 21) - 10;
if (c == 0) {
st.add(a);
br.add(a);
} else if (c == 1) {
st.add_x_minus_a(a);
br.add_x_minus_a(a);
} else if (c == 2) {
st.add_a_minus_x(a);
br.add_a_minus_x(a);
} else if (c == 3) {
st.add_abs(a);
br.add_x_minus_a(a);
br.add_a_minus_x(a);
} else if (c == 4) {
st.prefix_min();
br.prefix_min();
} else if (c == 5) {
st.suffix_min();
br.suffix_min();
} else {
long long b = (long long)(rng() % 11) - 5;
long long d = rng() % 6;
if (rng() % 2) {
st.shift(b);
br.shift(b, b);
shifted += std::abs(b);
} else {
st.shift(b, b + d);
br.shift(b, b + d);
shifted += std::abs(b) + d;
}
}
}
}
void check(const slope_trick<long long>& st, const brute& br, long long shifted) {
assert(shifted < B - W);
assert(st.min() == br.min());
assert(st.argmin() == br.argmin());
for (int x = -W; x <= W; x++) assert(st(x) == br.at(x));
}
int main() {
std::mt19937 rng(20261030);
for (int it = 0; it < 3000; it++) {
slope_trick<long long> st;
brute br;
long long shifted = 0;
int ops = rng() % 25;
for (int t = 0; t < ops; t++) {
random_ops(rng, st, br, 1, shifted);
check(st, br, shifted);
}
}
for (int it = 0; it < 2000; it++) {
slope_trick<long long> f, g;
brute bf, bg;
long long shifted = 0;
random_ops(rng, f, bf, rng() % 12, shifted);
random_ops(rng, g, bg, rng() % 12, shifted);
f.merge(g);
for (int x = -B; x <= B; x++) bf.at(x) += bg.at(x);
check(f, bf, shifted);
assert(g.min() == 0);
assert(!g.argmin().first && !g.argmin().second);
assert(g(7) == 0);
}
{
slope_trick<long long> f;
assert(f.min() == 0);
assert(!f.argmin().first && !f.argmin().second);
f.add_x_minus_a(3);
assert(f.argmin() == std::make_pair(std::optional<long long>(), std::optional<long long>(3)));
f.add_a_minus_x(-2);
assert(f.argmin() == std::make_pair(std::optional<long long>(-2), std::optional<long long>(3)));
f.add_abs(10);
assert(f.min() == 7);
assert(f.argmin() == std::make_pair(std::optional<long long>(3), std::optional<long long>(10)));
}
std::cout << "Hello World" << std::endl;
}