Submission #1247687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247687		Double_Slash	Flooding Wall (BOI24_wall)	C++20	70 / 100	5087 ms	289800 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()

const int M = 1e9 + 7;
int n, a[500001], b[500001], POW[500000]{1};

constexpr int fast(int x, int n) {
    if (not n) return 1;
    int ret = fast(x, n >> 1);
    ret = (ll) ret * ret % M;
    if (n & 1) ret = (ll) ret * x % M;
    return ret;
}

struct Val {
    ll iw, sum, prod = 1;
    int cnt;

    void init(int i, int A) {
        iw = sum = POW[i - 1] * (2 - A) % M;
        prod = A;
        cnt = 1;
    }

    Val operator+(const Val &o) {
        Val ret{};
        ret.iw = ((iw + sum * o.cnt) % M * o.prod + o.iw) % M;
        ret.sum = (sum * o.prod + o.sum) % M;
        ret.prod = prod * o.prod % M;
        ret.cnt = cnt + o.cnt;
        return ret;
    }
};

struct Prod {
    int n;
    vector<int> st;

    Prod(int n) : n(n), st(n << 1) {}

    void upd(int i) {
        for (++st[i += n]; i >>= 1;) st[i] = (ll) st[i << 1] * st[i << 1 | 1] % M;
    }

    int operator[](int i) { return st[i + n]; }

    int operator()(int l, int r) {
        int ret = 1;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ret = (ll) ret * st[l++] % M;
            if (r & 1) ret = (ll) ret * st[--r] % M;
        }
        return ret;
    }
};

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i) POW[i] = POW[i - 1] * 2 % M;
    map<int, vector<int>> m;
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        m[a[i]].emplace_back(i);
        (ans -= a[i]) %= M;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
        m[b[i]].emplace_back(i);
        (ans -= b[i]) %= M;
        if (a[i] > b[i]) swap(a[i], b[i]);
    }
    ans = (ll) ans * fast(2, n - 1) % M;
    auto calc = [&] {
        map<int, vector<int>> m;
        for (int i = 1; i <= n; ++i) {
            m[a[i]].emplace_back(i);
            m[b[i]].emplace_back(i);
        }
        vector<int> A(n + 1);
        set<int> s;
        for (int i = 1; i <= n; ++i) s.emplace(i);
        struct St {
            int n;
            vector<Val> st;

            St(int n) : n(n), st(n << 1) {
                for (int i = n; --i;) st[i + n].init(i, 0);
                for (int i = n; --i;) st[i] = st[i << 1] + st[i << 1 | 1];
            }

            void upd(int i, int v) {
                st[i + n].init(i, v);
                for (i += n; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
            }

            Val operator()(int l, int r) {
                Val lagg{}, ragg{};
                for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                    if (l & 1) lagg = lagg + st[l++];
                    if (r & 1) ragg = st[--r] + ragg;
                }
                return lagg + ragg;
            }
        } st{n + 1};
        Prod prod{n + 1};
        for (auto &[k, v]: m) {
            ll cur = 0;
            for (int i: v) {
                if (not A[i]++) s.erase(i);
                st.upd(i, A[i]);
                prod.upd(i);
                auto it = s.upper_bound(i);
                int lo = it == s.begin() ? 1 : *prev(it);
                cur += st(lo, i).iw * prod(i + 1, n + 1) % M;
            }
            (ans += cur % M * k % M) %= M;
        }
    };
    calc();
    Prod st{n + 1};
    for (auto &[k, v]: m) {
        sort(all(v));
        int pre[v.size()], in[v.size()], suf[v.size()];
        for (int i = v.size(); i--;) {
            pre[i] = st(1, v[i]);
            suf[i] = st(v[i] + 1, n + 1);
        }
        for (int i: v) st.upd(i);
        for (int i = v.size(); --i;) in[i - 1] = st(v[i - 1] + 1, v[i] + 1);
        int iw = 0, sum = 0;
        for (int r = 0; r < v.size(); ++r) {
            if (r) {
                iw = (ll) iw * in[r - 1] % M;
                sum = (ll) sum * in[r - 1] % M;
            }
            (iw += (ll) v[r] * pre[r] % M) %= M;
            (sum += pre[r]) %= M;
            (ans += ((ll) (v[r] + 1) * (sum + (st[v[r]] - 1) * pre[r])- (iw + (ll) v[r] * (st[v[r]] - 1) * pre[r] % M)) % M * fast(st[v[r]], M - 2) % M * k % M * suf[r] % M) %= M;
        }
    }
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    calc();
    cout << (ans % M + M) % M;
}

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