이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, C = 1e9 + 10, MOD = 1e9 + 7;
long long pw2[N];
void precalc()
{
pw2[0] = 1;
for (int i = 1; i < N; i++)
{
pw2[i] = pw2[i - 1] * 2 % MOD;
}
}
struct SegTree
{
int l, r, mid;
long long val_ = 0, lz = 1;
SegTree *lc, *rc;
SegTree(int l_, int r_) : l(l_), r(r_)
{
mid = (l + r) / 2;
val_ = r - l;
lc = rc = nullptr;
}
~SegTree()
{
if (lc)
{
free(lc);
}
if (rc)
{
free(rc);
}
}
void push()
{
lc = lc ? lc : new SegTree(l, mid);
rc = rc ? rc : new SegTree(mid, r);
(lc->lz *= lz) %= MOD;
(rc->lz *= lz) %= MOD;
lz = 1;
}
void pull()
{
val_ = (lc->val() + rc->val()) % MOD;
}
long long val()
{
return val_ * lz % MOD;
}
void multiply(int ll, int rr, int u)
{
if (ll <= l && rr >= r)
{
lz *= u;
return;
}
push();
if (ll < mid)
{
lc->multiply(ll, rr, u);
}
if (mid < rr)
{
rc->multiply(ll, rr, u);
}
pull();
}
};
int main()
{
precalc();
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
if (a[i] > b[i])
{
swap(a[i], b[i]);
}
}
long long ans = 0;
for (int i = 0; i < n; i++)
{
(ans += pw2[n - 1] * (b[i] - a[i] + (C - b[i]) * 2ll)) %= MOD;
}
{
SegTree st(0, C);
for (int i = 0; i < n; i++)
{
st.multiply(0, a[i], 0);
st.multiply(b[i], C, 2);
(ans += MOD - pw2[n - i - 1] * st.val() % MOD) %= MOD;
}
}
{
SegTree st(0, C);
for (int i = n - 1; i >= 0; i--)
{
st.multiply(0, a[i], 0);
st.multiply(b[i], C, 2);
(ans += MOD - pw2[i] * st.val() % MOD) %= MOD;
}
(ans += n * st.val() % MOD) %= MOD;
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |