Submission #1191442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191442		8pete8	Flooding Wall (BOI24_wall)	C++20	100 / 100	4743 ms	362760 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("O3,unroll-loops")
#define sz(x) (int)((x).size())
#define int long long

const int mod = 1e9+7, mxn = 1e6, inf = 1e9, minf = -1e9, lg = 30;

int n, val[mxn+10][2], P[mxn+10], sub[mxn+10][2];
vector<int> comp;

struct seg {
    int *dp, *waysx, *ways, (*lazy)[2];
    int size;

    seg(int sz) {
        size = sz;
        dp = new int[4*size+10]();
        waysx = new int[4*size+10]();
        ways = new int[4*size+10]();
        lazy = new int[4*size+10][2];
        for(int i=0; i<=4*size+9; ++i) {
            lazy[i][0] = 1;
            lazy[i][1] = 0;
        }
    }

    ~seg() {
        delete[] dp;
        delete[] waysx;
        delete[] ways;
        delete[] lazy;
    }

    inline void apply(int pos, pii x) {
        dp[pos] = (x.f * dp[pos] + x.s * waysx[pos]) % mod;
        waysx[pos] = (x.f * waysx[pos]) % mod;
        ways[pos] = (x.f * ways[pos]) % mod;
        int tmp = lazy[pos][0];
        lazy[pos][0] = (lazy[pos][0] * x.f) % mod;
        lazy[pos][1] = (lazy[pos][1] * x.f + tmp * x.s) % mod;
    }

    inline void push(int pos, int l, int r) {
        if (lazy[pos][0] == 1 && lazy[pos][1] == 0) return;
        if (l != r) {
            apply(pos<<1, {lazy[pos][0], lazy[pos][1]});
            apply(pos<<1|1, {lazy[pos][0], lazy[pos][1]});
        }
        lazy[pos][0] = 1;
        lazy[pos][1] = 0;
    }

    inline void pull(int pos) {
        dp[pos] = dp[pos<<1] + dp[pos<<1|1];
        if(dp[pos] >= mod) dp[pos] -= mod;
        waysx[pos] = waysx[pos<<1] + waysx[pos<<1|1];
        if(waysx[pos] >= mod) waysx[pos] -= mod;
        ways[pos] = ways[pos<<1] + ways[pos<<1|1];
        if(ways[pos] >= mod) ways[pos] -= mod;
    }

    void update(int ql, int qr, int k, int pos=1, int l=0, int r=-1) {
        if(r == -1) r = size;
        if(l > qr || r < ql) return;
        if(ql <= l && r <= qr) {
            apply(pos, {k, k});
            return;
        }
        push(pos, l, r);
        int m = (l + r) >> 1;
        update(ql, qr, k, pos<<1, l, m);
        update(ql, qr, k, pos<<1|1, m+1, r);
        pull(pos);
    }

    void modify(int qpos, int d, int w, int pos=1, int l=0, int r=-1) {
        if(r == -1) r = size;
        if(l > qpos || r < qpos) return;
        if(l == r) {
            dp[pos] = (dp[pos] + d) % mod;
            ways[pos] = (ways[pos] + w) % mod;
            waysx[pos] = (waysx[pos] + w * comp[l]) % mod;
            return;
        }
        push(pos, l, r);
        int m = (l + r) >> 1;
        modify(qpos, d, w, pos<<1, l, m);
        modify(qpos, d, w, pos<<1|1, m+1, r);
        pull(pos);
    }

    pii get_both(int ql, int qr, int pos=1, int l=0, int r=-1) {
        if(r == -1) r = size;
        if(l > qr || r < ql) return {0, 0};
        if(ql <= l && r <= qr) return {dp[pos], ways[pos]};
        push(pos, l, r);
        int m = (l + r) >> 1;
        pii left = get_both(ql, qr, pos<<1, l, m);
        pii right = get_both(ql, qr, pos<<1|1, m+1, r);
        return { (left.f + right.f) % mod, (left.s + right.s) % mod };
    }
};

int pref[mxn+10], suf[mxn+10];

struct fen {
    int *fwk, size;
    void init(int sz) {
        size = sz;
        fwk = new int[size+2]();
    }
    ~fen() { delete[] fwk; }
    void update(int pos, int val) {
        pos++;
        for(; pos <= size+1; pos += pos&-pos) fwk[pos] += val;
    }
    int qry(int pos) {
        pos++;
        int sum = 0;
        for(; pos > 0; pos -= pos&-pos) sum += fwk[pos];
        return sum;
    }
} tmx;

int32_t main() {
    fastio
    cin >> n;
    int ans = 0;
    P[0] = 1;
    comp.pb(0);
    for(int i=1; i<=n; ++i) P[i] = (P[i-1]*2) % mod;
    
    for(int i=1; i<=n; ++i) cin >> val[i][0];
    for(int i=1; i<=n; ++i) {
        cin >> val[i][1];
        if(val[i][0] > val[i][1]) swap(val[i][0], val[i][1]);
        comp.pb(val[i][0]);
        comp.pb(val[i][1]);
    }
    
    sort(all(comp));
    comp.erase(unique(all(comp)), comp.end());
    int sz = comp.size()-1;

    for(int i=1; i<=n; ++i) {
        val[i][0] = lb(all(comp), val[i][0]) - comp.begin();
        val[i][1] = lb(all(comp), val[i][1]) - comp.begin();
    }

    int total = 0;
    for(int i=1; i<=n; ++i)
        total = (total + comp[val[i][0]] + comp[val[i][1]]) % mod;
    ans = ((-P[n-1] * total) % mod + mod) % mod;

    pii upd[2];
    tmx.init(sz);
    for(int i=1; i<=n; ++i) tmx.update(val[i][1], 1);
    
    suf[n+1] = minf;
    for(int i=n; i>=1; --i) suf[i] = max(suf[i+1], val[i][0]);
    for(int i=1; i<=n; ++i) pref[i] = max(pref[i-1], val[i][0]);

    seg t_forward(sz);
    t_forward.modify(0, 0, 1);
    for(int i=1; i<=n; ++i) {
        tmx.update(val[i][1], -1);
        int v0 = val[i][0], v1 = val[i][1];
        int c0 = comp[v0], c1 = comp[v1];
        for(int k=0; k<2; ++k) {
            int v = k ? v1 : v0;
            if(suf[i+1] <= v-1) {
                int cnt = tmx.qry(v-1);
                int sum2 = P[cnt];
                pii res = t_forward.get_both(0, v);
                int sum = (res.f + res.s * comp[v]) % mod;
                ans = (ans + sum2 * sum) % mod;
                sub[i][k] = sum2;
            }
            upd[k] = t_forward.get_both(0, (k ? v1 : v0)-1);
        }
        
        t_forward.update(0, v0-1, 0);
        t_forward.update(v0, v1-1, 1);
        t_forward.update(v1, sz, 2);
        
        for(int k=0; k<2; ++k) {
            int v = k ? v1 : v0;
            int add = (upd[k].f + comp[v] * upd[k].s) % mod;
            t_forward.modify(v, add, upd[k].s);
        }
    }

    seg t_backward(sz);
    t_backward.modify(0, 0, 1);
    tmx.init(sz);
    for(int i=1; i<=n; ++i) tmx.update(val[i][1], 1);

    for(int i=n; i>=1; --i) {
        tmx.update(val[i][1], -1);
        int v0 = val[i][0], v1 = val[i][1];
        int c0 = comp[v0], c1 = comp[v1];
        for(int k=0; k<2; ++k) {
            int v = k ? v1 : v0;
            if(pref[i-1] <= v) {
                int cnt = tmx.qry(v);
                int sum2 = P[cnt];
                pii res = t_backward.get_both(0, v-1);
                int sum = (res.f + res.s * comp[v]) % mod;
                ans = (ans + sum2 * sum) % mod;
                ans = (ans - sub[i][k] * sum2 % mod * comp[v] % mod + mod) % mod;
            }
            upd[k] = t_backward.get_both(0, (k ? v1 : v0)-1);
        }
        
        t_backward.update(0, v0-1, 0);
        t_backward.update(v0, v1-1, 1);
        t_backward.update(v1, sz, 2);
        
        for(int k=0; k<2; ++k) {
            int v = k ? v1 : v0;
            int add = (upd[k].f + comp[v] * upd[k].s) % mod;
            t_backward.modify(v, add, upd[k].s);
        }
    }

    cout << ans;
    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