結果
問題 | No.2656 XOR Slimes |
ユーザー | as277575 |
提出日時 | 2024-03-01 22:34:08 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 32,920 bytes |
コンパイル時間 | 3,561 ms |
コンパイル使用メモリ | 237,936 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-29 14:33:29 |
合計ジャッジ時間 | 5,866 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 17 ms
6,820 KB |
testcase_09 | AC | 17 ms
6,816 KB |
testcase_10 | AC | 17 ms
6,820 KB |
testcase_11 | AC | 17 ms
6,816 KB |
testcase_12 | AC | 18 ms
6,820 KB |
testcase_13 | AC | 17 ms
6,820 KB |
testcase_14 | AC | 16 ms
6,816 KB |
testcase_15 | AC | 16 ms
6,820 KB |
testcase_16 | AC | 17 ms
6,820 KB |
testcase_17 | AC | 17 ms
6,816 KB |
testcase_18 | AC | 17 ms
6,816 KB |
testcase_19 | AC | 17 ms
6,816 KB |
testcase_20 | AC | 17 ms
6,816 KB |
testcase_21 | AC | 17 ms
6,816 KB |
testcase_22 | AC | 18 ms
6,816 KB |
testcase_23 | AC | 17 ms
6,820 KB |
testcase_24 | AC | 17 ms
6,816 KB |
testcase_25 | AC | 18 ms
6,820 KB |
testcase_26 | AC | 18 ms
6,816 KB |
testcase_27 | AC | 18 ms
6,820 KB |
testcase_28 | AC | 17 ms
6,816 KB |
testcase_29 | AC | 17 ms
6,820 KB |
testcase_30 | AC | 17 ms
6,820 KB |
testcase_31 | AC | 17 ms
6,820 KB |
testcase_32 | AC | 17 ms
6,816 KB |
testcase_33 | AC | 17 ms
6,820 KB |
testcase_34 | AC | 17 ms
6,820 KB |
testcase_35 | AC | 18 ms
6,816 KB |
testcase_36 | AC | 17 ms
6,816 KB |
testcase_37 | AC | 17 ms
6,816 KB |
testcase_38 | AC | 18 ms
6,820 KB |
testcase_39 | AC | 17 ms
6,816 KB |
testcase_40 | AC | 17 ms
6,816 KB |
testcase_41 | AC | 18 ms
6,820 KB |
testcase_42 | AC | 17 ms
6,820 KB |
testcase_43 | AC | 18 ms
6,820 KB |
testcase_44 | AC | 19 ms
6,820 KB |
testcase_45 | AC | 18 ms
6,816 KB |
testcase_46 | AC | 19 ms
6,816 KB |
testcase_47 | AC | 18 ms
6,820 KB |
testcase_48 | AC | 18 ms
6,816 KB |
testcase_49 | AC | 19 ms
6,820 KB |
testcase_50 | AC | 19 ms
6,820 KB |
testcase_51 | AC | 18 ms
6,816 KB |
testcase_52 | AC | 18 ms
6,820 KB |
testcase_53 | AC | 18 ms
6,816 KB |
testcase_54 | AC | 19 ms
6,816 KB |
testcase_55 | AC | 19 ms
6,820 KB |
testcase_56 | AC | 18 ms
6,816 KB |
testcase_57 | AC | 16 ms
6,816 KB |
testcase_58 | AC | 18 ms
6,816 KB |
ソースコード
#include <algorithm> #include <bit> #include <bitset> #include <cassert> #include <complex> #include <climits> #include <cstdio> #include <cstdlib> #include <cmath> #include <deque> #include <iostream> #include <map> #include <iomanip> #include <optional> #include <random> #include <ranges> #include <unordered_set> #include <unordered_map> #include <vector> #include <set> #include <string> #include <type_traits> #include <variant> using std::__gcd; using std::bitset; using std::cin; using std::cerr; using std::complex; using std::cout; using std::deque; using std::endl; using std::greater; using std::hash; using std::istream; using std::min; using std::map; using std::max; using std::multiset; using std::nullopt; using std::optional; using std::ostream; using std::pair; using std::rotate; using std::set; using std::setprecision; using std::string; using std::string_view; using std::swap; using std::tie; using std::to_string; using std::tuple; using std::unordered_map; using std::unordered_set; using std::vector; #if __cplusplus >= 201709L using std::ranges::sort; using std::ranges::views::iota; using std::views::reverse; using std::views::filter; using std::views::transform; #endif #define L(expr) ([&](const auto& _) { return (expr) ; }) #define Map(expr) (transform((L((expr))))) #define Filter(expr) (filter((L((expr))))) template <typename T> ostream& operator<< (ostream& o, const multiset<T>& v) { for (const auto& x : v) o << x << " "; return o; } template <typename T> ostream& operator<< (ostream& o, const unordered_set<T>& v) { o << "{"; for (const auto& x : v) o << x << " "; o << "}"; return o; } template<typename T, typename U> ostream& operator<< (ostream& o, const pair<T, U>& p) { o << "<" << p.first << ", " << p.second << ">"; return o; } template <typename T> ostream& operator<< (ostream& o, const vector<T>& v) { for (const auto& x : v) o << x << " "; return o; } template <typename T> ostream& operator<< (ostream& o, const set<T>& v) { for (const auto& x : v) o << x << " "; return o; } template <typename T> ostream& operator<< (ostream& o, const deque<T>& v) { for (const auto& x : v) o << x << " "; return o; } template <typename K, typename V> ostream& operator<<(ostream& o, const unordered_map<K, V>& m) { o << "{"; for (const auto& [k, v] : m) o << " " << k << ": " << v << ","; o << "}"; return o; } template <typename K, typename V> ostream& operator<<(ostream& o, const map<K, V>& m) { o << "{"; for (const auto& [k, v] : m) o << " " << k << ": " << v << ","; o << "}"; return o; } template <typename T> ostream& operator<< (ostream& o, const vector<vector<T>>& v) { for (const auto& x : v) o << x << endl; return o; } ostream& operator<< (ostream& o, const vector<string>& v) { for (const auto& x : v) o << x << endl; return o; } void print_to(ostream& o) { o << endl; }; template <typename T, typename... A> void print_to(ostream& o, const T& t, const A&... a) { o << t << " "; print_to(o, a...); } template <typename... A> void out(const A&... a) { print_to(cout, a...); } template <typename T, typename... A> const T& cerr_and_return(const T& t, const A&... a) { print_to(cerr, "\t", t, " ← ", a...); return t; } template <typename T, typename... A> T& cerr_and_return(T& t, const A&... a) { print_to(cerr, "\t", t, " ← ", a...); return t; } #ifdef DEBUG #define err(...) print_to(cerr, "\t[", #__VA_ARGS__, "]", " = ", __VA_ARGS__) #else #define err(...) #endif #ifdef DEBUG #define E(expr) (cerr_and_return((expr), (#expr))) #else #define E(expr) (expr) #endif class in { public: in() {} in(istream &i) : i(i) {} in(int n) : n(n) {} template <typename T> operator T () { T n; i >> n; return n; } template <typename T> operator deque<T> () { deque<T> v(n ? n.value() : static_cast<int>(*this)); for (auto& x : v) x = *this; return v; } template <typename T> operator multiset<T> () { return insert<multiset<T>>(n ? n.value() : static_cast<int>(*this)); } template <typename T, typename U> operator pair<T, U> () { return {*this, *this}; } template <typename T> operator complex<T> () { return {*this, *this}; } template <typename T> operator set<T> () { return insert<set<T>>(n ? n.value() : static_cast<int>(*this)); } template <typename T> operator vector<T> () { vector<T> v(n ? n.value() : static_cast<int>(*this)); for (auto& x : v) x = static_cast<T>(*this); return v; } private: template <typename S> S insert(int n) { S s; while (n--) s.insert(static_cast<typename S::key_type>(*this)); return s; } optional<int> n; istream& i = cin; } _; /* template <typename T> istream& operator>> (istream& i, T& t) { t = static_cast<T>(in(i)); return i; } */ // Test for complex integers modulo: pair<Mod<>, Mod<>> // https://yukicoder.me/problems/no/2651 template <typename T> using Complex = pair<T, T>; template <typename U, typename V> pair<U, V> operator += (pair<U, V>& p, const pair<U, V>& q) { p.first += q.first; p.second += q.second; return p; } template <typename U, typename V> pair<U, V> operator + (pair<U, V> p, const pair<U, V>& q) { return p += q; } template <typename U, typename V> pair<U, V> operator -= (pair<U, V>& p, const pair<U, V>& q) { p.first -= q.first; p.second -= q.second; return p; } template <typename U, typename V> pair<U, V> operator - (pair<U, V> p, const pair<U, V>& q) { return p -= q; } template <typename U, typename V> pair<U, V> operator * (pair<U, V> p, const pair<U, V>& q) { return p *= q; } template <typename U, typename V, typename W> pair<U, V> operator * (pair<U, V> p, const W& q) { return p *= q; } template <typename U, typename V, typename W> pair<U, V> operator * (const W& q, pair<U, V> p) { return {q * p.first, q * p.second}; } template <typename U, typename V> pair<U, V> operator *= (pair<U, V>& p, const pair<U, V>& q) { U new_first = p.first * q.first - p.second * q.second; V new_second = p.first * q.second + p.second * q.first; p.first = new_first; p.second = new_second; return p; } template <typename U, typename V, typename W> pair<U, V> operator *= (pair<U, V>& p, const W& q) { p.first *= q; p.second *= q; return p; } template <typename U, typename V> pair<U, V> operator / (pair<U, V> p, const pair<U, V>& q) { err("pair", p, "/", "pair", q); return p /= q; } template <typename U, typename V, typename W> pair<U, V> operator / (pair<U, V> p, const W& q) { err("pair", p, "/", "scalar", q); return p /= q; } template <typename U, typename V, typename W> pair<U, V> operator / (const W& q, pair<U, V> p) { return pair<U, V>{q, 0} / p; } template <typename S, typename T> complex<T> operator / (const S& s, complex<T> c) { return complex<T>{s, 0} / c; } template <typename U, typename V, typename W, typename X> pair<U, V> operator /= (pair<U, V>& p, const pair<W, X>& q) { err("pair", p, "/=", "pair", q); pair<W, X> c = {q.first, -q.second}; p *= c; auto m2 = q * c; assert(m2.second == 0); p /= m2.first; return p; } template <typename U, typename V, typename W> pair<U, V> operator /= (pair<U, V>& p, const W& q) { err("pair", p, "/=", "scalar", q); p.first /= q; p.second /= q; return p; } template <typename U, typename V> double hypot(const pair<U, V>& p) { return hypot(1.0 * p.first, 1.0 * p.second); } template <typename U, typename V> pair<U, V> conj(const pair<U, V>& p) { return {p.first, -p.second}; } template <typename U, typename V> struct std::hash<pair<U, V>> { std::size_t operator () (const pair<U, V>& p) const { return hash<U>{}(p.first) ^ (hash<V>{}(p.second) << 1); // https://en.cppreference.com/w/cpp/utility/hash } }; template <typename Element, typename... List> struct Contains { static constexpr bool value = false; }; template <typename Element, typename... List> struct Contains<Element, Element, List...> { static constexpr bool value = true; }; template <typename Element, typename Other, typename... List> struct Contains<Element, Other, List...> { static constexpr bool value = Contains<Element, List...>::value; }; template <typename... Args> inline constexpr bool contains_v = Contains<Args...>::value; struct Empty {}; #define TREE_SUM #define TREE_MULTIPLY template <typename V = long long> struct FastTree { using K = long long; const K a = -1e18, b = 1e18; struct Node { Node *left = nullptr, *right = nullptr; V value = 0; #ifdef TREE_SUM V sum_ = 0; #endif #ifdef TREE_MULTIPLY V multiplier = 1; #endif deque<string> to_lines(K a, K b) const { const K m = a + (b - a + 1) / 2 - 1; deque<string> lines = left ? left->to_lines(a, m) : deque<string>{}; if (right) { deque<string> right_lines = right->to_lines(m + 1, b); size_t pad = 0; for (string_view l : lines) pad = max(pad, l.size()); for (string& l : lines) l += string(pad - l.size(), ' ') + ']'; while (lines.size() < right_lines.size()) lines.push_back(string(pad + !!pad, ' ')); for (int i = 0; i < right_lines.size(); ++i) lines[i] += right_lines[i]; } lines.push_front("[" + to_string(a) + " " + to_string(b)); if (value != 0) lines[0] += (value >= 0 ? " +" : " ") + to_string(value); #ifdef TREE_MULTIPLY if (multiplier != 1) lines[0] += " *" + to_string(multiplier); #endif #ifdef TREE_SUM lines[0] += " s=" + to_string(sum_); #endif return lines; } } root; V operator[] (const K k) const { if (k < a || b < k) return 0; K a = this->a, b = this->b, m; const Node* node = &root; V r = 0; while (node) { r += node->value; m = a + (b - a + 1) / 2 - 1; if (k <= m) { b = m; node = node->left; } else { a = m + 1; node = node->right; } } return r; } #ifdef TREE_SUM V sum(const K l, const K r) const { static vector<tuple<K, K, const Node* #ifdef TREE_MULTIPLY , V #endif >> stack(128); int top = 0; stack[top] = {a, b, &root #ifdef TREE_MULTIPLY , 1 #endif }; K a, b, m; const Node* node; #ifdef TREE_MULTIPLY V multiplier; #endif V s = 0; while (top >= 0) { tie(a, b, node #ifdef TREE_MULTIPLY , multiplier #endif ) = stack[top--]; if (l <= a && b <= r) s += #ifdef TREE_MULTIPLY multiplier * #endif node->sum_; else { s += max(static_cast<K>(0), 1 + min(r, b) - max(l, a)) * node->value #ifdef TREE_MULTIPLY * multiplier #endif ; m = a + (b - a + 1) / 2 - 1; if (l <= m && a <= r && node->left) stack[++top] = {a, m, node->left #ifdef TREE_MULTIPLY , multiplier * node->multiplier #endif }; if (l <= b && m <= r && node->right) stack[++top] = {m + 1, b, node->right #ifdef TREE_MULTIPLY , multiplier * node->multiplier #endif }; } } return s; } #endif void add(const K l, const K r, V v) { static vector<tuple<K, K, Node*, char>> stack(128); int top = 0; stack[top] = {a, b, &root, 0}; K a, b, m; Node* node; bool visited; while (top >= 0) { tie(a, b, node, visited) = stack[top]; //err(a, b, node, top, l, r); if (visited) { --top; #ifdef TREE_MULTIPLY if (!(b < l || r < a) && !(l <= a && b <= r)) v *= node->multiplier; #endif //err("exiting", a, b, node->value); node->sum_ = node->value * (b - a + 1); if (node->left) node->sum_ += node->left->sum_ #ifdef TREE_MULTIPLY * node->multiplier #endif ; if (node->right) node->sum_ += node->right->sum_ #ifdef TREE_MULTIPLY * node->multiplier #endif ; } else { //err("entering", a, b); std::get<3>(stack[top]) = true; if (b < l || r < a); else if (l <= a && b <= r) { node->value += v; } else { #ifdef TREE_MULTIPLY v /= node->multiplier; #endif m = a + (b - a + 1) / 2 - 1; if (l <= m) { if (!node->left) node->left = new Node; stack[++top] = {a, m, node->left, false}; } if (m < r) { if (!node->right) node->right = new Node; stack[++top] = {m + 1, b, node->right, false}; } } } } } #ifdef TREE_MULTIPLY void multiply(const K l, const K r, const V v) { static vector<tuple<K, K, Node*, bool>> stack(128); int top = 0; stack[top] = {a, b, &root, false}; K a, b, m; Node* node; bool visited; while (top >= 0) { tie(a, b, node, visited) = stack[top]; //err(a, b, node, top, l, r); if (visited) { --top; //err("exiting", a, b, node->value); node->sum_ = node->value * (b - a + 1); if (node->left) node->sum_ += node->left->sum_ #ifdef TREE_MULTIPLY * node->multiplier #endif ; if (node->right) node->sum_ += node->right->sum_ #ifdef TREE_MULTIPLY * node->multiplier #endif ; } else { //err("entering", a, b); std::get<3>(stack[top]) = true; if (b < l || r < a); else if (l <= a && b <= r) { node->value *= v; node->multiplier *= v; } else { m = a + (b - a + 1) / 2 - 1; if (l <= m) { if (!node->left) node->left = new Node; stack[++top] = {a, m, node->left, false}; } if (m < r) { if (!node->right) node->right = new Node; stack[++top] = {m + 1, b, node->right, false}; } } } } } #endif friend ostream& operator << (ostream& o, const FastTree& t) { deque<string> lines = t.root.to_lines(t.a, t.b); size_t pad = 0; for (string_view l : lines) pad = max(pad, l.size()); for (string& l : lines) l += string(pad - l.size(), ' ') + ']'; for (string_view l : lines) o << l << endl; return o; } }; struct Sum {}; template <typename V = long long> struct Tree { const long long a, b; using Interval = pair<long long, long long>; inline static pair<Interval, Interval> split(const Interval& i) { auto [l, r] = i; long long m = l + (r - l + 1) / 2 - 1; return {{l, m}, {m + 1, r}}; } inline static bool in(const Interval& i, const Interval& j) { return j.first <= i.first && i.second <= j.second; } inline static bool disjoint(const Interval& i, const Interval& j) { return i.second < j.first || j.second < i.first; } inline static bool intersect(const Interval& i, const Interval& j) { return !disjoint(i, j); } struct Node { #ifdef TREE_MULTIPLY V subtree_multiplier = 1; #endif V value = 0 /*,, min_ = 0, max_ = 0 */; V sum_ = 0; Node *left = nullptr, *right = nullptr; ~Node() { if (left) delete left; if (right) delete right; } template <typename T> void set(const Interval& ni, long long l, const vector<T>& v) { Interval vi = {l, l + v.size() - 1}; if (disjoint(ni, vi)) return; assert(value == 0); #ifdef TREE_MULTIPLY assert(subtree_multiplier == 1); #endif if (ni.first == ni.second) { value = v[ni.first - l]; } else { auto [li, ri] = split(ni); if (intersect(li, vi)) { if (!left) left = new Node; left->set(li, l, v); } if (intersect(ri, vi)) { if (!right) right = new Node; right->set(ri, l, v); } } update(ni); } void set(const Interval& ni, const Interval& vi, V v) { if (disjoint(ni, vi)) return; if (in(ni, vi)) { value = v; #ifdef TREE_MULTIPLY subtree_multiplier = 1; #endif if (left) delete left; left = nullptr; if (right) delete right; right = nullptr; } else { v -= value; #ifdef TREE_MULTIPLY assert(subtree_multiplier != 0); v /= subtree_multiplier; #endif auto [li, ri] = split(ni); if (intersect(li, vi)) { if (!left) left = new Node; left->set(li, vi, v); } if (intersect(ri, vi)) { if (!right) right = new Node; right->set(ri, vi, v); } } update(ni); } void add(const Interval& ni, const Interval& vi, V v #ifdef TREE_MULTIPLY , V denominator #endif ) { if (disjoint(ni, vi)) return; if (in(ni, vi)) { value += v #ifdef TREE_MULTIPLY / denominator #endif ; } else { auto [li, ri] = split(ni); if (intersect(li, vi)) { if (!left) left = new Node; left->add(li, vi, v #ifdef TREE_MULTIPLY , denominator * subtree_multiplier #endif ); } if (intersect(ri, vi)) { if (!right) right = new Node; right->add(ri, vi, v #ifdef TREE_MULTIPLY , denominator * subtree_multiplier #endif ); } } update(ni); } void multiply(const Interval& ni, const Interval& vi, V v) { if (disjoint(ni, vi)) return; if (v == 0) { set(ni, vi, 0); } else if (in(ni, vi)) { value *= v; subtree_multiplier *= v; } else { auto [li, ri] = split(ni); if (!left) left = new Node; if (!right) right = new Node; left->add(li, li, value, subtree_multiplier); right->add(ri, ri, value, subtree_multiplier); value = 0; left->multiply(li, vi, v); right->multiply(ri, vi, v); } update(ni); } void get(const Interval& ni, const Interval& qi, vector<V>& result, #ifdef TREE_MULTIPLY V multiplier = 1, #endif V addition = 0) { if (disjoint(ni, qi)) return; V v = #ifdef TREE_MULTIPLY multiplier * #endif value + addition; if (ni.first == ni.second) { result.push_back(v); } else { const auto [li, ri] = split(ni); if (left) { left->get(li, qi, result, #ifdef TREE_MULTIPLY multiplier * subtree_multiplier, #endif v); } else { for (long long i = std::max(li.first, qi.first); i <= std::min(li.second, qi.second); ++i) result.push_back(v); } if (right) { right->get(ri, qi, result, #ifdef TREE_MULTIPLY multiplier * subtree_multiplier, #endif v); } else { for (long long i = std::max(ri.first, qi.first); i <= std::min(ri.second, qi.second); ++i) result.push_back(v); } } } V sum(const Interval& ni, const Interval& qi, bool cache=true) { if (disjoint(ni, qi)) return 0; if (in(ni, qi) && cache) return sum_; auto [li, ri] = split(ni); return value * (std::min(ni.second, qi.second) - std::max(ni.first, qi.first) + 1) + #ifdef TREE_MULTIPLY subtree_multiplier * #endif ( (left ? left->sum(li, qi) : 0) + (right ? right->sum(ri, qi) : 0)); } /* V min(const Interval& ni, const Interval& qi, bool cache=true) { assert(intersect(ni, qi)); if (in(ni, qi) && cache) return min_; auto [li, ri] = split(ni); V kids = 0; if (intersect(li, qi) && intersect(ri, qi)) kids = std::min(left ? left->min(li, qi) : 0, right ? right->min(ri, qi) : 0); else if (intersect(li, qi) && left) kids = left->min(li, qi); else if (intersect(ri, qi) && right) kids = right->min(ri, qi); return value + /*subtree_multiplier **/ /*kids; }*/ // UNTESTED /* V max(const Interval& ni, const Interval& qi, bool cache=true) { assert(intersect(ni, qi)); if (in(ni, qi) && cache) return max_; auto [li, ri] = split(ni); V kids = 0; if (intersect(li, qi) && intersect(ri, qi)) kids = std::max(left ? left->max(li, qi) : 0, right ? right->max(ri, qi) : 0); else if (intersect(li, qi) && left) kids = left->max(li, qi); else if (intersect(ri, qi) && right) kids = right->max(ri, qi); return value + /*subtree_multiplier * kids; }*/ void update(const Interval& i) { sum_ = sum(i, i, false); //max_ = max(i, i, false); //min_ = min(i, i, false); } /* void print() { if (left) left->print(); if (value) //cout << "[" << a << ", " << b << "; len=" << b - a + 1 << "] " << value << " " << sum_ << endl; if (right) right->print(); }*/ } root; Tree(long long a = -1e18, long long b = 1e18): a(a), b(b) {} void add(long long l, long long r, V v) { root.add({a, b}, {l, r}, v #ifdef TREE_MULTIPLY , 1 #endif ); } #ifdef TREE_MULTIPLY void multiply(long long l, long long r, V v) { root.multiply({a, b}, {l, r}, v); } #endif void set(long long l, long long r, V v) { root.set({a, b}, {l, r}, v); } template <typename T> void set(long long l, const vector<T>& v) { root.set({a, b}, l, v); } vector<V> get(long long l, long long r) { vector<V> result; result.reserve(r - l + 1); root.get({a, b}, {l, r}, result); return result; } V sum(long long l, long long r) { return root.sum({a, b}, {l, r}); } /* V max(long long l, long long r) { return root.max({a, b}, {l, r}); } V min(long long l, long long r) { return root.min({a, b}, {l, r}); }*/ }; auto read_undirected(int n, int m) { vector e(n + 1, vector<int>()); while (m--) { int u = _, v = _; e[u].push_back(v); e[v].push_back(u); } return e; } struct GraphSearchResult { GraphSearchResult(int size): d(size, -1), p(size), v_to_cc(size, -1) {}; vector<int> postorder, d, p, v_to_cc; vector<vector<int>> cc; }; GraphSearchResult dfs(const vector<vector<int>>& edges) { GraphSearchResult r(edges.size()); auto& [postorder, d, p, v_to_cc, cc] = r; vector<pair<int, int>> q; for (int s = 1; s < edges.size(); ++s) if (d[s] < 0) { cc.push_back({}); q.push_back({0, s}); while (q.size()) { auto [w, u] = q.back(); q.pop_back(); if (d[u] >= 0) continue; postorder.push_back(u); d[u] = d[w] + 1; p[u] = w; v_to_cc[u] = cc.size() - 1; cc.back().push_back(u); for (int v : edges[u]) q.push_back({u, v}); } } std::reverse(postorder.begin(), postorder.end()); return r; } vector<int> return_vertices(const vector<vector<int>>& edges, const GraphSearchResult& s) { vector<int> r(s.p.size(), -1); for (int u : s.postorder) { r[u] = u; int b = s.d[u]; for (int v : edges[u]) if (v != s.p[u]) { int c = s.p[v] == u ? r[v] : v; if (s.d[c] < b) { b = s.d[c], r[u] = c; } } } return r; } struct GcdResult { long long g; long long x; long long y; }; GcdResult extended_gcd(const long long aa, const long long bb) { assert(aa || bb); long long a = abs(aa), b = abs(bb); bool swapped = b > a; if (swapped) swap(a, b); static vector<long long> k(512); int i = 0; while (b) { k[i++] = a / b; a %= b; swap(a, b); } assert(i <= 512); long long x = 1, y = 0; while (i) { swap(x, y); y -= x * k[--i]; } if (swapped) swap(x, y); return {a, aa < 0 ? -x : x, bb < 0 ? -y : y}; } long long inv(long long a, long long m) { GcdResult r = extended_gcd(a, m); assert(r.g == 1); long long result = (r.x % m + m) % m; assert(0 <= result); assert(result < m); return result; } long long lcm(long long a, long long b) { return (a / std::gcd(a, b)) * b; } inline long long power(long long a, long long b, long long m) { long long r = 1; for (long long i = 0, e = (a % m); (1 << i) <= b; ++i, e = (e * e) % m) if (b & (1 << i)) r = (r * e) % m; return r; } struct Operators { /* inline friend auto operator -= (auto& f, const auto& g) { return f += -g; } inline friend auto operator /= (auto& f, const auto& g) { return f *= g.inv(); } */ }; struct Fraction : Operators { inline friend Fraction operator -= (Fraction& f, const Fraction& g) { return f += -g; } inline friend Fraction operator /= (Fraction& f, const Fraction& g) { return f *= g.inv(); } friend Fraction operator + (Fraction f, const Fraction& g) { return f += g; } friend Fraction operator - (Fraction f, const Fraction& g) { return f -= g; } friend Fraction operator * (Fraction f, const Fraction& g) { return f *= g; } friend Fraction operator / (Fraction f, const Fraction& g) { return f /= g; } friend bool operator == (const Fraction& f, const Fraction& g) { long long l = lcm(f.denominator, g.denominator); return f.numerator * (l / f.denominator) == g.numerator * (l / g.denominator); } friend bool operator < (const Fraction& f, const Fraction& g) { long long l = lcm(f.denominator, g.denominator); return f.numerator * (l / f.denominator) < g.numerator * (l / g.denominator); } long long numerator = 0, denominator = 1; Fraction() {} Fraction(long long n) : numerator(n) {} Fraction(long long n, long long d) : numerator(n), denominator(d) { simplify(); } Fraction operator += (const Fraction& f) { long long l = lcm(denominator, f.denominator); numerator = numerator * (l / denominator) + f.numerator * (l / f.denominator); denominator = l; simplify(); return *this; } Fraction operator - () const { return {-numerator, denominator}; } Fraction operator *= (const Fraction& f) { long long g1 = __gcd(numerator, f.denominator), n1 = numerator / g1, d1 = f.denominator / g1, g2 = __gcd(denominator, f.numerator), n2 = f.numerator / g2, d2 = denominator / g2; numerator = n1 * n2; denominator = d1 * d2; simplify(); return *this; } Fraction inv() const { return {denominator, numerator}; } void simplify() { long long g = __gcd(numerator, denominator); numerator /= g; denominator /= g; if (denominator < 0) { numerator = -numerator; denominator = -denominator; } } friend ostream& operator << (ostream& o, const Fraction& f) { o << f.numerator << "/" << f.denominator ; return o; } }; template <long long M=998244353> struct Mod { inline Mod<M> operator -= (Mod<M> g) { return value = (value + M - g.value) % M; } inline Mod<M> operator /= (Mod<M> g) { return value = (value * ::inv(g.value, M)) % M; } inline friend Mod<M> operator + (Mod<M> f, Mod<M> g) { return f += g; } inline friend Mod<M> operator - (Mod<M> f, Mod<M> g) { return f -= g; } inline friend Mod<M> operator * (Mod<M> f, Mod<M> g) { return f *= g; } inline friend Mod<M> operator / (Mod<M> f, Mod<M> g) { return f /= g; } inline friend bool operator == (Mod<M> f, Mod<M> g) { return f.value == g.value; } inline friend bool operator < (Mod<M> f, Mod<M> g) { return f.value < g.value; } long long value; inline Mod(long long v = 0) : value((M + v % M) % M) {} inline Mod<M> operator += (Mod<M> b) { value = (value + b.value) % M; return *this; } inline Mod<M> operator - () const { return M - value; } inline Mod<M> operator *= (Mod<M> b) { value = (value * b.value) % M; return *this; } inline Mod<M> inv() const { return ::inv(value, M); } inline friend ostream& operator << (ostream& o, Mod<M> a) { o << a.value; return o; } inline friend istream& operator >> (istream& i, Mod<M>& a) { return i >> a.value; } }; map<long long, long long> factorize(long long n) { map<long long, long long> r; for (long long i = 2; i * i <= n; ++i) for (; n % i == 0; n /= i) ++r[i]; if (n > 1) ++r[n]; return r; } template<typename T, typename U> auto cdiv(T t, U u) { return (t + u - 1) / u; } inline vector<int> subsets(int s) { vector<int> change; for (int t = s, b = 1 << __builtin_ctz(t) ; t; t ^= b, b = 1 << __builtin_ctz(t)) change.push_back(b - (s & (b - 1))); vector<int> r = {0}; int over = 1 << __builtin_popcount(s); for (int t = 1, st = 0; t < over; ++t) r.push_back(st += change[__builtin_ctz(t)]); return r; } const vector<pair<int, int>> four_directions {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; template <typename V> bool is_index(const vector<V>& v, int i, int j) { return 0 <= i && i < v.size() && 0 <= j && j < v[i].size(); } template <typename V> bool is_index(const vector<V>& v, pair<int, int> ij) { return is_index(v, ij.first, ij.second); } auto indices(const vector<string>& v) { vector<pair<int, int>> r; for (int i = 0; i < v.size(); ++i) for (int j = 0; j < v[i].size(); ++j) r.push_back({i, j}); return r; } auto four_neighbors(const vector<string>& b, pair<int, int> i) { vector<pair<int, int>> r; for (auto d : four_directions) if (is_index(b, i + d)) r.push_back(i + d); return r; } vector<string> get_rotated_clockwise(const vector<string>& t) { vector<string> r(t[0].size(), string(t.size(), ' ')); for (int i = 0; i < t.size(); ++i) for (int j = 0; j < t[0].size(); ++j) r[j][t.size() - i - 1] = t[i][j]; return r; } template <typename T> long long sum(const T& t) { return std::accumulate(begin(t), end(t), 0ll); } vector<long long> get_partial_sums(const vector<long long>& v) { vector<long long> p {0}; partial_sum(v.cbegin(), v.cend(), back_inserter(p)); return p; } void Yes(bool b) { out(b ? "Yes" : "No"); } // Wczytać wektor i inne kolekcje stringów void testTreeParity() { { const long long M = 2000000000; Tree t(-M, M); FastTree<long long> f{-M, M}; for (long long i = 0; ; ++i) { if (i % 100000 == 0) out(i); { long long a = rand() % M, b = rand() % M, v = rand() % M; if (a > b) swap(a, b); err("add", a, b, v); t.add(a, b, v); f.add(a, b, v); } { //cerr << f; long long k = rand() % M; long long tr = t.get(k, k)[0], fr = f[k]; err("get", k, tr, fr); assert(tr == fr); } #ifdef TREE_SUM { long long a = rand() % M, b = rand() % M; if (a > b) swap(a, b); long long tr = t.sum(a, b), fr = f.sum(a, b); if (tr != fr) { cerr << f; out("sum", a, b, tr, fr); } assert(tr == fr); } #endif #ifdef TREE_MULTIPLY { long long a = rand() % M, b = rand() % M, v = rand() % M; if (a > b) swap(a, b); err("multiply", a, b, v); t.multiply(a, b, v); f.multiply(a, b, v); } #endif } } } void testTreeSpeed() { { const int M = 2000000000; //Tree<long long> t; FastTree<long long> t; for (long long i = 0; i < 500000; ++i) { if (i % 100000 == 0) err(i); { long long a = rand() % M, b = rand() % M, v = rand() % M; if (a > b) swap(a, b); //err("add", a, b, v); t.add(a, b, v); } { //cerr << f; //long long k = rand() % M; //long long tr = t.sum(k, k);//t.get(k, k)[0]; //long long fr = t[k]; } { long long a = rand() % M, b = rand() % M; if (a > b) swap(a, b); t.sum(a, b); } } } } int main() { std::ios::sync_with_stdio(false); cout << setprecision(50); cerr << setprecision(50); int n = _; vector<long long> x = in(n), a = in(n); vector<long long> d(n, 1e18); long long c = 0; for (int j : iota(0, n)) { err(j); c ^= a[j]; d[j] = E(c + x[j] - x[0]); long long cc = c; for (int i : iota(0, j)) { err(i); E(E(cc) ^= E(a[i])); d[j] = min(d[j], E(d[E(i)]) + E(E(cc) + x[j] - x[i + 1])); } } err(d); out(d.back()); return 0; }