結果
問題 | No.2248 max(C)-min(C) |
ユーザー | nono00 |
提出日時 | 2023-03-17 22:40:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 440 ms / 3,000 ms |
コード長 | 3,428 bytes |
コンパイル時間 | 1,127 ms |
コンパイル使用メモリ | 101,972 KB |
実行使用メモリ | 11,740 KB |
最終ジャッジ日時 | 2023-10-18 15:38:34 |
合計ジャッジ時間 | 15,260 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 3 ms
4,348 KB |
testcase_04 | AC | 3 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 5 ms
4,348 KB |
testcase_07 | AC | 5 ms
4,348 KB |
testcase_08 | AC | 5 ms
4,348 KB |
testcase_09 | AC | 5 ms
4,348 KB |
testcase_10 | AC | 2 ms
4,348 KB |
testcase_11 | AC | 5 ms
4,348 KB |
testcase_12 | AC | 3 ms
4,348 KB |
testcase_13 | AC | 5 ms
4,348 KB |
testcase_14 | AC | 5 ms
4,348 KB |
testcase_15 | AC | 5 ms
4,348 KB |
testcase_16 | AC | 3 ms
4,348 KB |
testcase_17 | AC | 5 ms
4,348 KB |
testcase_18 | AC | 378 ms
10,948 KB |
testcase_19 | AC | 45 ms
4,416 KB |
testcase_20 | AC | 440 ms
11,740 KB |
testcase_21 | AC | 421 ms
11,476 KB |
testcase_22 | AC | 281 ms
9,628 KB |
testcase_23 | AC | 178 ms
7,056 KB |
testcase_24 | AC | 68 ms
4,944 KB |
testcase_25 | AC | 394 ms
11,212 KB |
testcase_26 | AC | 352 ms
10,420 KB |
testcase_27 | AC | 397 ms
10,948 KB |
testcase_28 | AC | 37 ms
4,348 KB |
testcase_29 | AC | 365 ms
10,684 KB |
testcase_30 | AC | 137 ms
6,528 KB |
testcase_31 | AC | 440 ms
11,740 KB |
testcase_32 | AC | 78 ms
5,208 KB |
testcase_33 | AC | 128 ms
5,736 KB |
testcase_34 | AC | 439 ms
11,740 KB |
testcase_35 | AC | 439 ms
11,740 KB |
testcase_36 | AC | 434 ms
11,740 KB |
testcase_37 | AC | 218 ms
7,584 KB |
testcase_38 | AC | 417 ms
11,740 KB |
testcase_39 | AC | 415 ms
11,740 KB |
testcase_40 | AC | 414 ms
11,740 KB |
testcase_41 | AC | 353 ms
10,684 KB |
testcase_42 | AC | 414 ms
11,740 KB |
testcase_43 | AC | 364 ms
10,880 KB |
testcase_44 | AC | 414 ms
11,740 KB |
testcase_45 | AC | 318 ms
10,156 KB |
testcase_46 | AC | 162 ms
7,056 KB |
testcase_47 | AC | 417 ms
11,740 KB |
testcase_48 | AC | 339 ms
11,740 KB |
testcase_49 | AC | 439 ms
11,740 KB |
testcase_50 | AC | 437 ms
11,740 KB |
testcase_51 | AC | 437 ms
11,740 KB |
testcase_52 | AC | 435 ms
11,740 KB |
testcase_53 | AC | 66 ms
4,944 KB |
ソースコード
#include <algorithm> #include <functional> #include <iostream> #include <utility> #include <vector> namespace nono { template <typename T> class SegmentTree { public: SegmentTree(const int size, const std::function<T(T, T)> op, const std::function<T()> e) : op_(op), e_(e) { init(size); } SegmentTree(const std::vector<T> &vec, const std::function<T(T, T)> op, const std::function<T()> e) : op_(op), e_(e) { int n = vec.size(); init(n); for (int i = 0; i < size_; --i) { data_[i + size_] = vec[i]; } for (int i = size_ - 1; i > 0; --i) { data_[i] = op_(data_[i << 1], data_[(i << 1) + 1]); } } void set(int i, const T value) { i += size_; data_[i] = value; update(i); } void add(int i, const T delta) { i += size_; data_[i] += delta; update(i); } T get_all() const { return data_[1]; } T get_range(int l, int r) const { T result_l = e_(), result_r = e_(); l += size_; r += size_; while (l < r) { if (l & 1) { result_l = op_(result_l, data_[l++]); } if (r & 1) { result_r = op_(data_[--r], result_r); } l >>= 1; r >>= 1; } return op_(result_l, result_r); } T operator[](int i) const { return data_[i + size_]; } private: const std::function<T(T, T)> op_; const std::function<T()> e_; int size_; std::vector<T> data_; void init(int n) { int log = 1; while (n > (1 << log)) ++log; size_ = 1 << log; data_.assign(2 * size_, e_()); } void update(int i) { i >>= 1; while (i > 0) { data_[i] = op_(data_[i << 1], data_[(i << 1) + 1]); i >>= 1; } } }; } // namespace nono int main() { constexpr int inf = 1e9 + 1; int n; std::cin >> n; std::vector<int> a(n), b(n); std::vector<std::pair<int, int>> order; order.reserve(3 * n); for (int i = 0; i < n; i++) std::cin >> a[i]; for (int i = 0; i < n; i++) std::cin >> b[i]; if (n == 1) { std::cout << 0 << '\n'; return 0; } for (int i = 0; i < n; i++) { order.emplace_back(a[i], i); order.emplace_back(b[i], i); order.emplace_back((a[i] + b[i]) / 2, i); } std::sort(order.begin(), order.end()); auto op = [](const int i, const int j) { return i < j ? i : j; }; auto e = [&]() { return inf; }; nono::SegmentTree<int> segtree(n, op, e); for (int i = 0; i < n; i++) { segtree.set(i, -1); } int ans = inf; for (const auto &[v, i]: order) { int l = 0 < i ? segtree.get_range(0, i) : inf; int r = i + 1 < n ? segtree.get_range(i + 1, n) : inf; if (l != -1 && r != -1) { ans = std::min(ans, v - std::min(l, r)); } segtree.set(i, v); // std::cout << "_________" << '\n'; // std::cout << "v: " << v << ", i: " << i << '\n'; // std::cout << "l: " << l << ", r: " << r << '\n'; // std::cout << ans << '\n'; // for (int j = 0; j < n; j++) { // std::cout << segtree[j] << ' '; // } // std::cout << '\n'; } std::cout << ans << '\n'; }