제출 #1028566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028566		GrandTiger1729	Flooding Wall (BOI24_wall)	C++17	100 / 100	1507 ms	763980 KiB

Main

#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 (lz == 0)
        {
            return;
        }
        if (ll <= l && rr >= r)
        {
            (lz *= u) %= MOD;
            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;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30