結果
問題 | No.2248 max(C)-min(C) |
ユーザー |
![]() |
提出日時 | 2023-03-17 22:07:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 803 ms / 3,000 ms |
コード長 | 18,441 bytes |
コンパイル時間 | 2,543 ms |
コンパイル使用メモリ | 209,268 KB |
最終ジャッジ日時 | 2025-02-11 13:15:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#line 2 "library/KowerKoint/stl-expansion.hpp"#include <bits/stdc++.h>template <typename T1, typename T2>std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {is >> p.first >> p.second;return is;}template <typename T, size_t N>std::istream& operator>>(std::istream& is, std::array<T, N>& a) {for (size_t i = 0; i < N; ++i) {is >> a[i];}return is;}template <typename T>std::istream& operator>>(std::istream& is, std::vector<T>& v) {for (auto& e : v) is >> e;return is;}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {os << p.first << " " << p.second;return os;}template <typename T, size_t N>std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {for (size_t i = 0; i < N; ++i) {os << a[i] << (i + 1 == a.size() ? "" : " ");}return os;}template <typename T>std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {for (size_t i = 0; i < v.size(); ++i) {os << v[i] << (i + 1 == v.size() ? "" : " ");}return os;}#line 3 "library/KowerKoint/base.hpp"using namespace std;#define REP(i, n) for(int i = 0; i < (int)(n); i++)#define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++)#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(),(a).rend()#define END(...) { print(__VA_ARGS__); return; }using VI = vector<int>;using VVI = vector<VI>;using VVVI = vector<VVI>;using ll = long long;using VL = vector<ll>;using VVL = vector<VL>;using VVVL = vector<VVL>;using ull = unsigned long long;using VUL = vector<ull>;using VVUL = vector<VUL>;using VVVUL = vector<VVUL>;using VD = vector<double>;using VVD = vector<VD>;using VVVD = vector<VVD>;using VS = vector<string>;using VVS = vector<VS>;using VVVS = vector<VVS>;using VC = vector<char>;using VVC = vector<VC>;using VVVC = vector<VVC>;using P = pair<int, int>;using VP = vector<P>;using VVP = vector<VP>;using VVVP = vector<VVP>;using LP = pair<ll, ll>;using VLP = vector<LP>;using VVLP = vector<VLP>;using VVVLP = vector<VVLP>;template <typename T>using PQ = priority_queue<T>;template <typename T>using GPQ = priority_queue<T, vector<T>, greater<T>>;constexpr int INF = 1001001001;constexpr ll LINF = 1001001001001001001ll;constexpr int DX[] = {1, 0, -1, 0};constexpr int DY[] = {0, 1, 0, -1};void print() { cout << '\n'; }template<typename T>void print(const T &t) { cout << t << '\n'; }template<typename Head, typename... Tail>void print(const Head &head, const Tail &... tail) {cout << head << ' ';print(tail...);}#ifdef DEBUGvoid dbg() { cerr << '\n'; }template<typename T>void dbg(const T &t) { cerr << t << '\n'; }template<typename Head, typename... Tail>void dbg(const Head &head, const Tail &... tail) {cerr << head << ' ';dbg(tail...);}#elsetemplate<typename... Args>void dbg(const Args &... args) {}#endiftemplate<typename T>vector<vector<T>> split(typename vector<T>::const_iterator begin, typename vector<T>::const_iterator end, T val) {vector<vector<T>> res;vector<T> cur;for(auto it = begin; it != end; it++) {if(*it == val) {res.push_back(cur);cur.clear();} else cur.push_back(*it);}res.push_back(cur);return res;}vector<string> split(typename string::const_iterator begin, typename string::const_iterator end, char val) {vector<string> res;string cur = "";for(auto it = begin; it != end; it++) {if(*it == val) {res.push_back(cur);cur.clear();} else cur.push_back(*it);}res.push_back(cur);return res;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template <typename T>pair<VI, vector<T>> compress(const vector<T> &a) {int n = a.size();vector<T> x;REP(i, n) x.push_back(a[i]);sort(ALL(x)); x.erase(unique(ALL(x)), x.end());VI res(n);REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin();return make_pair(res, x);}template <typename It>auto rle(It begin, It end) {vector<pair<typename It::value_type, int>> res;if(begin == end) return res;auto pre = *begin;int num = 1;for(auto it = begin + 1; it != end; it++) {if(pre != *it) {res.emplace_back(pre, num);pre = *it;num = 1;} else num++;}res.emplace_back(pre, num);return res;}template <typename It>vector<pair<typename It::value_type, int>> rle_sort(It begin, It end) {vector<typename It::value_type> cloned(begin, end);sort(ALL(cloned));auto e = rle(ALL(cloned));sort(ALL(e), [](const auto& l, const auto& r) { return l.second < r.second; });return e;}template <typename T>pair<vector<T>, vector<T>> factorial(int n) {vector<T> res(n+1), rev(n+1);res[0] = 1;REP(i, n) res[i+1] = res[i] * (i+1);rev[n] = 1 / res[n];for(int i = n; i > 0; i--) {rev[i-1] = rev[i] * i;}return make_pair(res, rev);}#line 3 "library/KowerKoint/integer/extgcd.hpp"constexpr ll extgcd(ll a, ll b, ll& x, ll& y) {x = 1, y = 0;ll nx = 0, ny = 1;while(b) {ll q = a / b;ll r = a % b;a = b, b = r;ll nnx = x - q * nx;ll nny = y - q * ny;x = nx, nx = nnx;y = ny, ny = nny;}return a;}#line 3 "library/KowerKoint/integer/pow-mod.hpp"constexpr ll inv_mod(ll n, ll m) {n %= m;if (n < 0) n += m;ll x = -1, y = -1;if(extgcd(n, m, x, y) != 1) throw logic_error("");x %= m;if(x < 0) x += m;return x;}constexpr ll pow_mod(ll a, ll n, ll m) {if(n == 0) return 1LL;if(n < 0) return inv_mod(pow_mod(a, -n, m), m);a %= m;if (a < 0) n += m;ll res = 1;while(n) {if(n & 1) {res *= a;res %= m;}n >>= 1;a *= a;a %= m;}return res;}#line 3 "library/KowerKoint/algebra/field.hpp"template <typename T>struct SumGroupBase {constexpr static bool defzero = false;using Coef = nullptr_t;using Scalar = nullptr_t;};template <typename T>struct ProdGroupBase {constexpr static bool defone = false;};template <typename T>struct RepresentationBase {using R = T;constexpr static T construct(const R& x) { return x; }constexpr static R represent(const T& x) { return x; }};template <typename T>struct CompareBase {constexpr static bool eq(const T& x, const T& y) { return x == y; }constexpr static bool lt(const T& x, const T& y) { return x < y; }};template <typename T>struct FinitePropertyBase {constexpr static bool is_finite = false;};template <typename T, typename SumGroup = SumGroupBase<T>, typename ProdGroup = ProdGroupBase<T>, typename Representation = RepresentationBase<T>,typename Compare = CompareBase<T>, typename FiniteProperty = FinitePropertyBase<T>>struct Field {using R = typename Representation::R;using Coef = typename SumGroup::Coef;using Scalar = typename SumGroup::Scalar;T val;constexpr static Field zero() {return SumGroup::zero;}constexpr static Field one() {return ProdGroup::one;}constexpr static bool defzero = SumGroup::defzero;constexpr static bool defone = ProdGroup::defone;constexpr static bool is_finite = FiniteProperty::is_finite;constexpr Field() {if constexpr(SumGroup::defzero) val = SumGroup::zero;else if constexpr(SumGroup::defone) val = ProdGroup::one;else val = T();}constexpr Field(const R& r) : val(Representation::construct(r)) {}constexpr R represent() const { return Representation::represent(val); }constexpr decltype(auto) operator[](size_t i) const {return val[i];}constexpr static Field premitive_root() {return FiniteProperty::premitive_root();}constexpr static size_t order() {return FiniteProperty::order();}constexpr Field& operator*=(const Field& other) {ProdGroup::mulassign(val, other.val);return *this;}constexpr Field operator*(const Field& other) const {return Field(*this) *= other;}constexpr Field inv() const {return ProdGroup::inv(val);}constexpr Field& operator/=(const Field& other) {return *this *= other.inv();}constexpr Field operator/(const Field& other) const {return Field(*this) /= other;}constexpr Field pow(ll n) const {if(n < 0) {return inv().pow(-n);}Field res = one();Field a = *this;while(n > 0) {if(n & 1) res *= a;a *= a;n >>= 1;}return res;}constexpr Field operator+() const {return *this;}constexpr Field& operator+=(const Field& other) {SumGroup::addassign(val, other.val);return *this;}constexpr Field operator+(const Field& other) const {return Field(*this) += other;}constexpr Field operator-() const {return SumGroup::minus(val);}constexpr Field& operator-=(const Field& other) {return *this += -other;}constexpr Field operator-(const Field& other) const {return Field(*this) -= other;}constexpr Field& operator++() {return *this += one();}Field operator++(int) {Field ret = *this;++*this;return ret;}constexpr Field& operator--() {return *this -= one();}Field operator--(int) {Field ret = *this;--*this;return ret;}constexpr Field& operator*=(const Coef& other) {SumGroup::coefassign(val, other);return *this;}constexpr Field operator*(const Coef& other) const {return Field(*this) *= other;}constexpr Scalar dot(const Field& other) const {return SumGroup::dot(val, other.val);}constexpr Scalar norm() const {return dot(*this);}constexpr bool operator==(const Field& other) const {return Compare::eq(val, other.val);}constexpr bool operator!=(const Field& other) const {return !(*this == other);}constexpr bool operator<(const Field& other) const {return Compare::lt(represent(), other.represent());}constexpr bool operator>(const Field& other) const {return other < *this;}constexpr bool operator<=(const Field& other) const {return !(*this > other);}constexpr bool operator>=(const Field& other) const {return !(*this < other);}friend istream& operator>>(istream& is, Field& f) {R r; is >> r;f = r;return is;}friend ostream& operator<<(ostream& os, const Field& f) {return os << f.represent();}};namespace std {template <typename T>struct hash<Field<T>> {size_t operator()(const Field<T>& f) const {return hash<typename Field<T>::R>()(f.represent());}};}template <typename>struct is_field : false_type {};template <typename T, typename SumGroup, typename ProdGroup, typename Representation, typename FiniteProperty>struct is_field<Field<T, SumGroup, ProdGroup, Representation, FiniteProperty>> : true_type {};template <typename T>constexpr bool is_field_v = is_field<T>::value;template <typename T>constexpr T zero() {if constexpr(is_field_v<T>) return T::zero();else return 0;}template <typename T>constexpr T one() {if constexpr(is_field_v<T>) return T::one();else return 1;}template <typename T>constexpr bool is_finite() {if constexpr(is_field_v<T>) return T::is_finite;else return false;}#line 4 "library/KowerKoint/algebra/modint.hpp"template <ll mod>struct SumGroupModint : SumGroupBase<ll> {static ll& addassign(ll& l, const ll& r) {ll ret;if(__builtin_add_overflow(l, r, &ret)) {l = l % mod + r % mod;} else {l = ret;}return l;}constexpr static bool defzero = true;constexpr static ll zero = 0;constexpr static ll minus(const ll& x) {return -x;}};template <ll mod>struct ProdGroupModint : ProdGroupBase<ll> {constexpr static bool defmul = true;static ll& mulassign(ll& l, const ll& r) {ll ret;if(__builtin_mul_overflow(l, r, &ret)) {l = (l % mod) * (r % mod);} else {l = ret;}return l;}constexpr static bool defone = true;constexpr static ll one = 1;constexpr static bool definv = true;constexpr static ll inv(const ll& x) {return inv_mod(x, mod);}};template <ll mod>struct RepresentationModint : RepresentationBase<ll> {using R = ll;constexpr static ll construct(const R& x) { return x % mod; }constexpr static R represent(const ll& x) {ll ret = x % mod;if(ret < 0) ret += mod;return ret;}};template <ll mod>struct CompareModint : CompareBase<ll> {constexpr static bool lt(const ll& l, const ll& r) {return RepresentationModint<mod>::represent(l) < RepresentationModint<mod>::represent(r);}constexpr static bool eq(const ll& l, const ll& r) {return RepresentationModint<mod>::represent(l) == RepresentationModint<mod>::represent(r);}};template <ll mod>struct FinitePropertyModint : FinitePropertyBase<ll> {constexpr static bool is_finite = true;constexpr static ll premitive_root() {static_assert(mod == 998244353);return 3;}constexpr static size_t order() {return mod - 1;}};template <ll mod>using Modint = Field<ll, SumGroupModint<mod>, ProdGroupModint<mod>, RepresentationModint<mod>, CompareModint<mod>, FinitePropertyModint<mod>>;using MI3 = Modint<998244353>;using V3 = vector<MI3>;using VV3 = vector<V3>;using VVV3 = vector<VV3>;using MI7 = Modint<1000000007>;using V7 = vector<MI7>;using VV7 = vector<V7>;using VVV7 = vector<VV7>;#line 3 "library/KowerKoint/counting/counting.hpp"template <typename T>struct Counting {vector<T> fact, ifact;Counting() {}Counting(ll n) {assert(n >= 0);expand(n);}void expand(ll n) {assert(n >= 0);ll sz = (ll)fact.size();if(sz > n) return;fact.resize(n+1);ifact.resize(n+1);fact[0] = 1;FOR(i, max(1LL, sz), n+1) fact[i] = fact[i-1] * i;ifact[n] = fact[n].inv();for(ll i = n-1; i >= sz; i--) ifact[i] = ifact[i+1] * (i+1);}T p(ll n, ll r) {if(n < r) return 0;assert(r >= 0);expand(n);return fact[n] * ifact[n-r];}T c(ll n, ll r) {if(n < r) return 0;assert(r >= 0);expand(n);return fact[n] * ifact[r] * ifact[n-r];}T h(ll n, ll r) {assert(n >= 0);assert(r >= 0);return c(n+r-1, r);}T stirling(ll n, ll k) {if(n < k) return 0;assert(k >= 0);if(n == 0) return 1;T res = 0;T sign = k%2? -1 : 1;expand(k);REP(i, k+1) {res += sign * ifact[i] * ifact[k-i] * T(i).pow(n);sign *= -1;}return res;}vector<vector<T>> stirling_table(ll n, ll k) {assert(n >= 0 && k >= 0);vector<vector<T>> res(n+1, vector<T>(k+1));res[0][0] = 1;FOR(i, 1, n+1) FOR(j, 1, k+1) {res[i][j] = res[i-1][j-1] + j * res[i-1][j];}return res;}T bell(ll n, ll k) {assert(n >= 0 && k >= 0);expand(k);vector<T> tmp(k+1);T sign = 1;tmp[0] = 1;FOR(i, 1, k+1) {sign *= -1;tmp[i] = tmp[i-1] + sign * ifact[i];}T res = 0;REP(i, k+1) {res += T(i).pow(n) * ifact[i] * tmp[k-i];}return res;}vector<vector<T>> partition_table(ll n, ll k) {assert(n >= 0 && k >= 0);vector<vector<T>> res(n+1, vector<T>(k+1));REP(i, k+1) res[0][i] = 1;FOR(i, 1, n+1) FOR(j, 1, k+1) {res[i][j] = res[i][j-1] + (i<j? 0 : res[i-j][j]);}return res;}};#line 2 "Contests/yukicoder_381/yukicoder_381_c/main.cpp"/* #include <atcoder/all> *//* using namespace atcoder; *//* #include "KowerKoint/expansion/ac-library/all.hpp" */void solve(){int n; cin >> n;VL a(n), b(n); cin >> a >> b;REP(i, n) if(a[i] > b[i]) swap(a[i], b[i]);ll ok = INF, ng = -1;while(ok - ng > 1) {int mid = (ok+ng) / 2;VLP kukan(1, LP(-LINF, LINF));REP(i, n) {VLP kukan2;auto push_kukan2 = [&](int l, int r) {if(!kukan2.empty() && kukan2.back().second >= l) kukan2.back().second = r;else kukan2.emplace_back(l, r);};push_kukan2(a[i] - mid, a[i] + 1);push_kukan2((a[i]+b[i])/2 - mid, (a[i]+b[i])/2 + 1);push_kukan2(b[i] - mid, b[i] + 1);VLP new_kukan;for(auto& p : kukan) {for(auto& p2 : kukan2) {if(p.second <= p2.first || p2.second <= p.first) continue;new_kukan.emplace_back(max(p.first, p2.first), min(p.second, p2.second));}}kukan = new_kukan;}if(!kukan.empty()) ok = mid;else ng = mid;}print(ok);}// generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator)int main() {// Fasterize input/output scriptios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(100);// scanf/printf user should delete this fasterize input/output scriptint t = 1;//cin >> t; // comment out if solving multi testcasefor(int testCase = 1;testCase <= t;++testCase){solve();}return 0;}