/************************************* * author: marvinthang * * created: 03.12.2025 20:26:43 * *************************************/ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define left ___left___ #define right ___right___ #define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u) #define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u) #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } #ifdef LOCAL #include "debug.h" #else #define DB(...) #define db(...) "" #define debug(...) #endif namespace std { template <class U, class V> scan_op(pair <U, V>) { return in >> u.first >> u.second; } template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; } template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.first << ", " << u.second << ')'; } template <size_t i, class T> ostream &print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template <class...U> print_op(tuple <U...>) { return print_tuple_utils<0, tuple <U...>>(out, u); } template <class Con, class = decltype(begin(declval<Con>()))>typename enable_if <!is_same<Con, string>::value, ostream &>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; } template <class T> print_op(stack <T>) { vector <T> v; stack <T> st = u; while (!st.empty()) v.push_back(st.top()), st.pop(); reverse(v.begin(), v.end()); return out << v; } template <class T> print_op(queue <T>) { queue <T> q = u; out << '{'; while (!q.empty()) { out << q.front(); q.pop(); if (!q.empty()) out << ", "; } out << '}'; return out; } template <class T, class X, class Y> print_op(priority_queue <T, X, Y>) { priority_queue <T, X, Y> pq = u; out << '{'; while (!pq.empty()) { out << pq.top(); pq.pop(); if (!pq.empty()) out << ", "; } out << '}'; return out; } template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {} template <class...Args> decltype(auto)operator()(Args &&...args) { return fun_(ref(*this), forward<Args>(args)...); } }; template <class Fun> decltype(auto)y_combinator(Fun &&fun) { return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun)); } template <typename T, int D> struct Vec: public vector <Vec<T, D - 1>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template <typename ...Args> Vec(int n = 0, Args ...args): vector <Vec<T, D - 1>>(n, Vec<T, D - 1>(args...)) {} }; template <typename T> struct Vec<T, 1>: public vector<T>{ Vec(int n = 0, const T &val = T()): vector<T>(n, val) {} }; #if __cplusplus < 202002L template <class T> int ssize(const T &a) { return a.size(); } #endif } namespace MODINT { struct barrett { unsigned int _m; unsigned long long im; explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {} unsigned int umod() const { return _m; }; unsigned int mul(unsigned int a, unsigned int b) const { unsigned long long z = a; z *= b; unsigned long long x = (unsigned long long)(((unsigned __int128) z * im) >> 64); unsigned long long y = x * _m; return (unsigned int)(z - y + (z < y ? _m : 0)); } }; template <class T> T invGeneral(T a, T b) { a %= b; if (!a) return b == 1 ? 0 : -1; T x = invGeneral(b, a); return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b; } template <int m, enable_if_t<1 <= m>* = nullptr> struct static_modint { using mint = static_modint; public: static constexpr int mod() { return m; } static mint raw(int v) { mint x; x.v = v; return x; } static_modint(): v(0) {} template <class T> static_modint(T x) { int y; if (x < 0) { if (x < -mod()) y = x % mod(); else y = x; if (y < 0) y += mod(); } else { if (x < mod()) y = x; else y = x % mod(); } v = y; } unsigned int val() const { return v; } unsigned int operator () () const { return v; } mint & operator ++ () { if (++v == umod()) v = 0; return *this; } mint & operator -- () { if (!v) v = umod(); --v; return *this; } mint operator ++ (int) { mint old = *this; ++*this; return old; } mint operator -- (int) { mint old = *this; --*this; return old; } mint operator + () { return *this; } mint operator - () { return raw(!v ? 0 : umod() - v); } mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; } mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; } mint & operator *= (const mint &rhs) { unsigned long long z = v; z *= rhs.v; v = z % umod(); return *this; } mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); } friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } mint pow(long long n) const { assert(0 <= n); mint res = 1, a = *this; for (; n; n >>= 1, a *= a) if (n & 1) res *= a; return res; } mint inv() const { int i = invGeneral((int) v, mod()); assert(~i); return i; } friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; } friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; } friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; } friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; } explicit operator bool() const { return v; } explicit operator int() const { return v; } private: unsigned int v; static constexpr unsigned int umod() { return m; } }; template <int id> struct dynamic_modint { using mint = dynamic_modint; public: static int mod() { return (int) bt.umod(); } static void set_mod(int m) { assert(1 <= m); bt = barrett(m); } static mint raw(int v) { mint x; x.v = v; return x; } dynamic_modint(): v(0) {} template <class T> dynamic_modint(T x) { int y; if (x < 0) { if (x < -mod()) y = x % mod(); else y = x; if (y < 0) y += mod(); } else { if (x < mod()) y = x; else y = x % mod(); } v = y; } unsigned int val() const { return v; } unsigned int operator () () const { return v; } mint & operator ++ () { if (++v == umod()) v = 0; return *this; } mint & operator -- () { if (!v) v = umod(); --v; return *this; } mint operator ++ (int) { mint old = *this; ++*this; return old; } mint operator -- (int) { mint old = *this; --*this; return old; } mint operator + () { return *this; } mint operator - () { return raw(!v ? 0 : umod() - v); } mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; } mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; } mint & operator *= (const mint &rhs) { v = bt.mul(v, rhs.v); return *this; } mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); } friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; } friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; } friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; } friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; } mint pow(long long n) const { assert(0 <= n); mint res = 1, a = *this; for (; n; n >>= 1, a *= a) if (n & 1) res *= a; return res; } mint inv() const { int i = invGeneral((int) v, mod()); assert(~i); return i; } friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; } friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; } friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; } friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; } explicit operator bool() const { return v; } explicit operator int() const { return v; } private: unsigned int v; static barrett bt; static unsigned int umod() { return bt.umod(); } }; template <int id> barrett dynamic_modint<id>::bt(998244353); using modint998244353 = static_modint<998244353>; using modint1000000007 = static_modint<1000000007>; using modint = dynamic_modint <-1>; using Modular = modint1000000007; } using namespace MODINT; template < class S, // node data type S (*op) (S, S), // combine 2 nodes S (*e) (), // identity element class F, // lazy propagation tag S (*mapping) (F, S), // apply tag F on a node F (*composition) (F, F), // combine 2 tags F (*id)() // identity tag > struct LazySegTree { LazySegTree() : LazySegTree(0) {} LazySegTree(int n) : LazySegTree(vector<S>(n, e())) {} LazySegTree(const vector <S> &v) : n(v.size()) { log = 0; while ((1 << log) < n) ++log; size = 1 << log; d = vector<S>(size << 1, e()); lz = vector<F>(size, id()); for (int i = 0; i < n; ++i) d[i + size] = v[i]; for (int i = size - 1; i > 0; --i) update(i); } // 0 <= p < n void set(int p, S x) { assert(0 <= p && p < n); p += size; for (int i = log; i > 0; --i) push(p >> i); d[p] = x; for (int i = 1; i <= log; ++i) update(p >> i); } // 0 <= p < n S get(int p) { assert(0 <= p && p < n); p += size; for (int i = log; i > 0; --i) push(p >> i); return d[p]; } // Get product in range [l, r-1] // 0 <= l <= r <= n // For empty segment (l == r) -> return e() S prod(int l, int r) { assert(0 <= l && l <= r && r <= n); if (l == r) return e(); l += size; r += size; for (int i = log; i > 0; --i) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } // 0 <= p < n void apply(int p, F f) { assert(0 <= p && p < n); p += size; for (int i = log; i > 0; --i) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; ++i) update(p >> i); } // Apply f on all elements in range [l, r-1] // 0 <= l <= r <= n void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= n); if (l == r) return; l += size; r += size; for (int i = log; i > 0; --i) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; for (int i = 1; i <= log; ++i) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } // Binary search on SegTree to find largest r: // f(op(a[l] .. a[r-1])) = true (assuming empty array is always true) // f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false) template <bool (*g)(S)> int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= n); assert(g(e())); if (l == n) return n; l += size; for (int i = log; i > 0; --i) push(l >> i); S sm = e(); do { while (!(l & 1)) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = l << 1; if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return n; } // Binary search on SegTree to find smallest l: // f(op(a[l] .. a[r-1])) = true (assuming empty array is always true) // f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false) template <bool (*g)(S)> int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= n); assert(g(e())); if (!r) return 0; r += size; for (int i = log; i > 0; --i) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r & 1)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = r << 1 | 1; if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int n, size, log; vector<S> d; vector<F> lz; void update(int k) { d[k] = op(d[k << 1], d[k << 1 | 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(k << 1, lz[k]); all_apply(k << 1 | 1, lz[k]); lz[k] = id(); } }; template< class T, // data type for nodes T (*op) (T, T), // operator to combine 2 nodes T (*e)() // identity element > struct SegTree { SegTree(): SegTree(0) {} SegTree(int n) : SegTree(vector<T>(n, e())) {} SegTree(const vector <T>& v) : n(v.size()) { log = 0; while ((1 << log) < n) ++log; size = 1 << log; d = vector<T>(size << 1, e()); for (int i = 0; i < n; ++i) d[size + i] = v[i]; for (int i = size - 1; i > 0; --i) update(i); } // 0 <= p < n void set(int p, T x) { assert(0 <= p && p < n); p += size; d[p] = x; for (int i = 1; i <= log; ++i) update(p >> i); } // 0 <= p < n T get(int p) const { assert(0 <= p && p < n); return d[p + size]; } // Get product in range [l, r-1] // 0 <= l <= r <= n // For empty segment (l == r) -> return e() T prod(int l, int r) const { assert(0 <= l && l <= r && r <= n); T sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } T all_prod() const { return d[1]; } // Binary search on SegTree to find largest r: // f(op(a[l] .. a[r-1])) = true (assuming empty array is always true) // f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false) template <bool (*f)(T)> int max_right(int l) const { return max_right(l, [](T x) { return f(x); }); } template <class F> int max_right(int l, F f) const { assert(0 <= l && l <= n); assert(f(e())); if (l == n) return n; l += size; T sm = e(); do { while (!(l & 1)) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = l << 1; if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return n; } // Binary search on SegTree to find smallest l: // f(op(a[l] .. a[r-1])) = true (assuming empty array is always true) // f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false) template <bool (*f)(T)> int min_left(int r) const { return min_left(r, [](T x) { return f(x); }); } template <class F> int min_left(int r, F f) const { assert(0 <= r && r <= n); assert(f(e())); if (r == 0) return 0; r += size; T sm = e(); do { r--; while (r > 1 && (r & 1)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = r << 1 | 1; if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int n, size, log; vector <T> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; // end of template Modular sum(Modular a, Modular b) { return a + b; } Modular zero() { return 0; } Modular mul(Modular f, Modular x) { return x * f; } Modular one() { return 1; } void process(void) { int n; cin >> n; vector <int> a(n), b(n); cin >> a >> b; vector <pair <int, int>> lst; for (int i = 0; i < n; ++i) { lst.emplace_back(a[i], i); lst.emplace_back(b[i], i); } sort(lst.rbegin(), lst.rend()); Modular res; Modular inv2 = Modular(2).inv(); vector <Modular> init(n, 2); LazySegTree<Modular, sum, zero, Modular, mul, mul, one> left(n), right(n); SegTree<Modular, mul, one> mul(init); vector <int> cnt(n); int last = lst.back().first; for (auto [h, i]: lst) { res += (last - h) * (left.all_prod() + right.all_prod()); res -= h * Modular(2).pow(n - 1); if (!cnt[i]) { left.set(i, (-i + 1) * Modular(2).pow(n - i - 1) * mul.prod(0, i)); left.apply(i + 1, n, inv2); right.set(i, i * Modular(2).pow(i) * mul.prod(i + 1, n)); right.apply(0, i, inv2); } else { left.apply(i, i + 1, 2); left.apply(i + 1, n, 0); right.apply(i, i + 1, 2); right.apply(0, i, 0); } ++cnt[i]; mul.set(i, 2 - cnt[i]); last = h; } res += last * (left.all_prod() + right.all_prod()); cout << res << '\n'; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr); file("wall"); // int t; cin >> t; while (t--) process(); // cerr << "Time elapsed: " << TIME << " s.\n"; return (0^0); }

Main.cpp: In function 'int main()':
Main.cpp:16:62: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:526:9: note: in expansion of macro 'file'
  526 |         file("wall");
      |         ^~~~
Main.cpp:16:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | #define     file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:526:9: note: in expansion of macro 'file'
  526 |         file("wall");
      |         ^~~~