結果

問題 No.2248 max(C)-min(C)
ユーザー ruthen71
提出日時 2023-03-17 23:38:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 168 ms / 3,000 ms
コード長 4,535 bytes
コンパイル時間 2,108 ms
コンパイル使用メモリ 208,632 KB
最終ジャッジ日時 2025-02-11 14:34:37
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#ifdef _RUTHEN
#include <debug.hpp>
#else
#define show(...) true
#endif
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class Monoid> struct SegmentTree {
public:
using S = typename Monoid::value_type;
SegmentTree() : SegmentTree(0) {}
SegmentTree(int n) : SegmentTree(std::vector<S>(n, Monoid::e())) {}
SegmentTree(const std::vector<S>& v) : _n((int)v.size()) {
log = 0;
while ((1U << log) < (unsigned int)(_n)) log++;
size = 1 << log;
d = std::vector<S>(size << 1, Monoid::e());
for (int i = 0; i < _n; i++) d[i + size] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, const S& x) {
assert(0 <= p and p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
void chset(int p, const S& x) {
assert(0 <= p and p < _n);
p += size;
d[p] = Monoid::op(d[p], x);
for (int i = 1; i <= log; i++) update(p >> i);
}
S operator[](int p) const {
assert(0 <= p and p < _n);
return d[p + size];
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l and l <= r and r <= _n);
S sml = Monoid::e(), smr = Monoid::e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = Monoid::op(sml, d[l++]);
if (r & 1) smr = Monoid::op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return Monoid::op(sml, smr);
}
S all_prod() const { return d[1]; }
template <class F> int max_right(int l, F& f) const {
assert(0 <= l and l <= _n);
assert(f(Monoid::e()));
if (l == _n) return _n;
l += size;
S sm = Monoid::e();
do {
while ((l & 1) == 0) l >>= 1;
if (!f(Monoid::op(sm, d[l]))) {
while (l < size) {
l <<= 1;
if (f(Monoid::op(sm, d[l]))) {
sm = Monoid::op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = Monoid::op(sm, d[l]);
l++;
} while ((l & -l) != l); // 20false
return _n;
}
template <class F> int min_left(int r, F& f) const {
assert(0 <= r and r <= _n);
assert(f(Monoid::e()));
if (r == 0) return 0;
r += size;
S sm = Monoid::e();
do {
r--;
while (r > 1 and (r & 1)) r >>= 1;
if (!f(Monoid::op(d[r], sm))) {
while (r < size) {
r = (r << 1) | 1;
if (f(Monoid::op(d[r], sm))) {
sm = Monoid::op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = Monoid::op(d[r], sm);
} while ((r & -r) != r); // 20false
return 0;
}
private:
int _n, log, size;
std::vector<S> d;
inline void update(int k) { d[k] = Monoid::op(d[k << 1], d[(k << 1) | 1]); }
};
template <class S> struct MonoidMax {
using value_type = S;
static constexpr S op(S a, S b) { return std::max(a, b); }
static constexpr S e() { return std::numeric_limits<S>::lowest(); }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
V<long long> A(N), B(N);
rep(i, N) cin >> A[i];
rep(i, N) cin >> B[i];
V<long long> C(N);
rep(i, N) {
if (A[i] > B[i]) swap(A[i], B[i]);
C[i] = (A[i] + B[i]) / 2;
}
V<tuple<long long, int, int>> G;
rep(i, N) {
G.push_back({A[i], 0, i});
G.push_back({C[i], 1, i});
G.push_back({B[i], 2, i});
}
SegmentTree<MonoidMax<long long>> seg(N);
rep(i, N) seg.set(i, A[i]);
sort(G.begin(), G.end());
constexpr long long INF = 1LL << 60;
long long ans = INF;
for (auto [v, t, i] : G) {
ans = min(ans, seg.all_prod() - v);
if (t == 0) {
seg.set(i, C[i]);
} else if (t == 1) {
seg.set(i, B[i]);
} else {
seg.set(i, INF);
}
}
cout << ans << '\n';
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0