Submission #1099051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099051		_8_8_	Flooding Wall (BOI24_wall)	C++17	100 / 100	3116 ms	103272 KiB

Main

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

const int  N = 1e6 + 12, MOD = (int)1e9 + 7;


int n, a[N], b[N], m, ai[N], bi[N];
ll st[N];
void add(ll &x, ll y) {
    x += y;
    if(x >= MOD) x -= MOD;
}

vector<ll> c;

void prec() {
    for(int i = 1; i <= n; i++) {
        c.push_back(a[i]);
        c.push_back(b[i]);
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    m = (int)c.size();
    for(int i = 1; i <= n; i++) {
        ai[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin() + 1;
        bi[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin() + 1;
    }
    st[0] = 1;
    for(int i = 1; i <= n; i++) {
        st[i] = st[i - 1] ;
        add(st[i], st[i]);
    }
}
void rev() {
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    reverse(ai + 1, ai + n + 1);
    reverse(bi + 1, bi + n + 1);
}
ll res = 0;

ll t[N * 4], f[N * 4], mul[N * 4], dp[N * 4];

void build(int v = 1, int tl = 0, int tr = m) {
    mul[v] = 1;
    dp[v] = 0;
    t[v] =0;
    if(tl == tr) {
        if(tl) f[v] = c[tl - 1];
        else f[v] = 1;
    } else {
        int tm = (tl + tr) >> 1;
        build(v + v, tl, tm);
        build(v + v + 1, tm + 1, tr);
        f[v] = f[v + v];
        add(f[v], f[v + v + 1]);
    }
}

void inc(int v, int val) {
    mul[v] = (mul[v] * 1ll * val) % MOD;
    t[v] = t[v] * val % MOD;
    dp[v] = (dp[v] * val) % MOD;
}

void push(int v) {
    if(mul[v] != 1) {
        inc(v + v, mul[v]);
        inc(v + v + 1, mul[v]);
        mul[v] = 1;
    }
}
void upd(int l, int r, int v =  1, int tl = 0, int tr = m) {
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        inc(v, 2);
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l, r, v + v, tl, tm);
        upd(l, r, v + v + 1, tm + 1, tr);
        t[v] = t[v + v];add(t[v], t[v + v + 1]);
        dp[v] = dp[v + v];add(dp[v], dp[v + v + 1]);
    }
}
void upd1(int pos, ll val, int v = 1, int tl = 0, int tr = m) {
    if(tl == tr) {
        if(val == -1) {
            dp[v] = t[v] = 0;
        } else {
            add(dp[v], val);
            
            t[v] = dp[v] * f[v] % MOD;
        }
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd1(pos, val, v + v, tl, tm);
        else upd1(pos, val, v + v + 1, tm + 1, tr);
        t[v] = t[v + v];add(t[v], t[v + v + 1]);
        dp[v] = dp[v + v];add(dp[v], dp[v + v + 1]);
    }
    
}
ll get1(int l, int r, int v = 1, int tl = 0, int tr = m) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) return dp[v];
    push(v);
    int tm = (tl + tr) >> 1;
    ll ret = get1(l, r, v + v, tl, tm);
    add(ret, get1(l, r, v + v + 1, tm + 1, tr));
    return ret;
}
ll get(int l, int r, int v = 1, int tl = 0, int tr = m) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) return t[v];
    push(v);
    int tm = (tl + tr) >> 1;
    ll ret = get(l, r, v + v, tl, tm);
    add(ret, get(l, r, v + v + 1, tm + 1, tr));
    return ret;
}
void solve(bool fi = true) {
    vector<ll> d(m + 1, 0);
    d[0] = 1;
    build();
    upd1(0, 1);
    ll ans = 0;
    int it = 0;
    for(int i = 1; i <= n; i++) {
        ll S = get1(0, ai[i] - 1), _S = get1(0, bi[i] - 1);
        while(it < ai[i]) {
            upd1(it, -1);
            it++;
        }
        upd(bi[i], m);
        upd1(ai[i], S);
        upd1(bi[i], _S);
        ll K = 0;
        // for(int j = 1; j <= m; j++) {
        //     add(res, d[j] * c[j - 1] % MOD * st[n - i] % MOD);
        // }
        add(res, t[1] * st[n - i] % MOD);
    }
    if(fi) {
        ll v = t[1];
        res -= v * 1ll * n % MOD;
        if(res < 0) {
            res += MOD;
        }
        // for(int i = 1; i <= m; i++) {
        //     ll v = d[i] * c[i -1] % MOD * 1ll * n % MOD;
        //     res -= v;
        //     if(res < 0) {
        //         res += MOD;
        //     }
        // }
    }
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> b[i];    
        if(a[i] > b[i]) {
            swap(a[i], b[i]);
        }
    }

    prec();
    solve(1);
    rev();
    solve(0);
    ll v = 1, sum= 0;
    for(int i = 1; i <= n; i++) {
        add(sum, a[i]);
        add(sum, b[i]);
        if(i < n) {
            add(v, v);
        }
    }
    v = v * sum % MOD;
    res = (res - v + MOD) % MOD;
    cout << res << '\n';
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve(bool)':
Main.cpp:142:12: warning: unused variable 'K' [-Wunused-variable]
  142 |         ll K = 0;
      |            ^
Main.cpp:131:8: warning: unused variable 'ans' [-Wunused-variable]
  131 |     ll ans = 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