Submission #1326234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326234		nxk02102010	Flooding Wall (BOI24_wall)	C++20	100 / 100	735 ms	111568 KiB

Main

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

#define N 505050
#define int long long

const int p = 1e9 + 7;
const int inv2 = (p + 1) >> 1;

int n, m;
int b[N], a[N], lsh[N << 1], tot;
int pw[N], f[N], g[N], c[N];

struct seg {
    #define lc x << 1
    #define rc x << 1 | 1

    int s[N << 2], lz[N << 2];

    void chg(int x, int k) {
        s[x] = s[x] * k % p;
        lz[x] = lz[x] * k % p;
    }

    void pushdown(int x) {
        if (lz[x] == 1) return;
        chg(lc, lz[x]);
        chg(rc, lz[x]);
        lz[x] = 1;
    }

    void build(int x, int l, int r) {
        lz[x] = 1;
        s[x] = (r - l + 1) * pw[n] % p;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
    }

    void change(int x, int l, int r, int L, int R, int k) {
        if (L <= l && r <= R) {
            chg(x, k);
            return;
        }
        pushdown(x);
        int mid = (l + r) >> 1;
        if (L <= mid) change(lc, l, mid, L, R, k);
        if (mid < R) change(rc, mid + 1, r, L, R, k);
        s[x] = (s[lc] + s[rc]) % p;
    }

    int find(int x, int l, int r, int L, int R) {
        if (L <= l && r <= R) return s[x];
        pushdown(x);
        int mid = (l + r) >> 1;
        if (L <= mid && mid < R)
            return (find(lc, l, mid, L, R) + find(rc, mid + 1, r, L, R)) % p;
        if (L <= mid) return find(lc, l, mid, L, R);
        return find(rc, mid + 1, r, L, R);
    }
} le, ri;

vector<int> pos[N << 1];

int posl = 0, posr = 0, cnt = 0, ans = 0;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    pw[0] = 1;
    for (int i = 1; i <= n + 1; i++)
        pw[i] = pw[i - 1] * 2 % p;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lsh[++tot] = a[i];
        ans = (ans + p - pw[n - 1] * a[i] % p) % p;
    }

    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        lsh[++tot] = b[i];
        ans = (ans + p - pw[n - 1] * b[i] % p) % p;
    }

    sort(lsh + 1, lsh + tot + 1);
    tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;

    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(lsh + 1, lsh + tot + 1, a[i]) - lsh;
        b[i] = lower_bound(lsh + 1, lsh + tot + 1, b[i]) - lsh;
        pos[a[i]].push_back(i);
        pos[b[i]].push_back(i);
    }

    int c1 = 0;
    le.build(1, 1, n);
    ri.build(1, 1, n);

    for (int x = tot; x; x--) {
        for (int i : pos[x]) {
            ++c[i];
            if (c[i] == 2) {
                if (!posl) {
                    posl = posr = i;
                    le.build(1, 1, n);
                    ri.build(1, 1, n);
                    for (int j = 1; j <= i; j++)
                        if (c[j] == 1) le.change(1, 1, n, j, i, inv2);
                    for (int j = i; j <= n; j++)
                        if (c[j] == 1) ri.change(1, 1, n, i, j, inv2);
                    continue;
                }
                posl = min(posl, i);
                posr = max(posr, i);
                continue;
            }
            ++c1;
            if (!posl) {
                if (i > 1) le.change(1, 1, n, 1, i - 1, inv2);
                if (i < n) ri.change(1, 1, n, i + 1, n, inv2);
                continue;
            }

            if (i <= posl) le.change(1, 1, n, i, posl, inv2);
            if (i >= posr) ri.change(1, 1, n, posr, i, inv2);
        }
        int ad = lsh[x] - lsh[x - 1];
        if (!posl) {
            int res = pw[n - c1] * n % p + n * pw[n] % p - le.s[1] - ri.s[1];
            res = (res + pw[n + 1] - pw[n - c1 + 1]) % p;
            res = (res % p + p) % p;
            ans = (ans + ad * res) % p;
            continue;
        }

        int res = n * pw[n] % p - (posl > 1 ? le.find(1,1,n,1,posl - 1) : 0) - (posr < n ? ri.find(1,1,n,posr + 1,n) : 0);
        res =(res % p + p) % p; 
        ans = (ans + ad * res) % p;
    }

    ans = (ans % p + p) % p;
    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