Submission #1281458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281458		lightentheshadow	Flooding Wall (BOI24_wall)	C++20	100 / 100	866 ms	51016 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e5 + 5;
const long long mod = 1e9 + 7;

long long power[maxN];
int n, a[maxN], b[maxN], cnt[maxN];

struct segTree {
    long long st[maxN << 2], lz[maxN << 2];

    void build(int id, int l, int r) {
        lz[id] = 1;
        if (l == r) {
            st[id] = power[n];
            return ;
        }

        int mid = (l + r) >> 1;

        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);

        st[id] = st[id << 1] + st[id << 1 | 1];
        if (st[id] >= mod) st[id] -= mod;
    }

    void down(int id) {
        st[id << 1] = (st[id << 1] * lz[id]) % mod;
        st[id << 1 | 1] = (st[id << 1 | 1] * lz[id]) % mod;

        lz[id << 1] = (lz[id << 1] * lz[id]) % mod;
        lz[id << 1 | 1] = (lz[id << 1 | 1] * lz[id]) % mod;

        lz[id] = 1;
    }

    void update(int id, int l, int r, int u, int v, long long val) {
        if (v < l || r < u) return ;

        if (u <= l && r <= v) {
            if (st[id] == 0) return ;
            st[id] = (st[id] * val) % mod;
            lz[id] = (lz[id] * val) % mod;
            return ;
        }

        if (lz[id] != 1) down(id);
        int mid = (l + r) >> 1;

        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);

        st[id] = st[id << 1] + st[id << 1 | 1];
        if (st[id] >= mod) st[id] -= mod;
    }
} lt, rt;

bool cmp(pair<int, int> A, pair<int, int> B) {
    return A.first > B.first;
}
vector<pair<int, int>> query;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    power[0] = 1;
    for (int i = 1; i <= n; i++)
        power[i] = (power[i - 1] + power[i - 1]) % mod;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        query.push_back({a[i], i});
        query.push_back({b[i], i});
        cnt[i] = 2;
    }

    sort(query.begin(), query.end(), cmp);

    lt.build(1, 1, n);
    rt.build(1, 1, n);
//    cout << lt.st[1] << ' ' << rt.st[1] << '\n';

    int pre = max(*max_element(a + 1, a + n + 1), *max_element(b + 1, b + n + 1));
    long long ans = 0, empty_full = power[n], wall_blocked = 0, revPow = 500000004;
    for (auto [layer, i]: query) {
//        cout << "? " << layer << ' ' << i << '\n';
        if (pre != layer) {
            long long total = 1LL * n * power[n] % mod;
            long long emptyLR = (lt.st[1] + rt.st[1] - 1LL * n * empty_full) % mod;
            emptyLR += wall_blocked; if (emptyLR >= mod) emptyLR -= mod;
            total = total - emptyLR; if (total < 0) total += mod;
            ans = (ans + 1LL * (pre - layer) * total) % mod;
        }

        cnt[i]--;
        long long update_mul = (cnt[i] == 1 ? revPow : 0);
        lt.update(1, 1, n, i, n, update_mul);
        rt.update(1, 1, n, n - i + 1, n, update_mul);

        wall_blocked += power[n - 1];
        if (wall_blocked >= mod) wall_blocked -= mod;

        empty_full = (empty_full * update_mul) % mod;
        pre = layer;
    }

    long long total = 1LL * n * power[n] % mod;
    long long emptyLR = (lt.st[1] + rt.st[1] - 1LL * n * empty_full) % mod;
    emptyLR += wall_blocked; if (emptyLR >= mod) emptyLR -= mod;
    total = total - emptyLR; if (total < 0) total += mod;
    ans = (ans + 1LL * (pre - 1) * total) % 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