제출 #1167981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167981		Iskachun	Flooding Wall (BOI24_wall)	C++20	100 / 100	2795 ms	101448 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int  N = 1e6 + 12, mod = 1e9 + 7;
ll n, a[N], b[N], m, a2[N], b2[N];
ll st[N];
vector<ll> c;

void precalc () {
    for (ll 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 = c.size();
    for (ll i = 1; i <= n; i++) {
        a2[i] = lower_bound(c.begin(), c.end(), a[i]) - c.begin() + 1;
        b2[i] = lower_bound(c.begin(), c.end(), b[i]) - c.begin() + 1;
    }
    st[0] = 1;
    for (ll i = 1; i <= n; i++) st[i] = (st[i - 1] + st[i - 1]) % mod;
}
void rev () {
    reverse(a + 1, a + n + 1), reverse(a2 + 1, a2 + n + 1);
    reverse(b + 1, b + n + 1), reverse(b2 + 1, b2 + n + 1);
}
ll res = 0;

ll t[N * 4], f[N * 4], mul[N * 4], dp[N * 4];
void build (ll v = 1, ll left = 0, ll right = m) {
    mul[v] = 1, dp[v] = 0, t[v] = 0;
    if (left == right) {
        if (left) f[v] = c[left - 1];
        else f[v] = 1;
    } else {
        ll mid = (left + right) / 2;
        build(2 * v, left, mid), build(2 * v + 1, mid + 1, right);
        f[v] = (f[2 * v] + f[2 * v + 1]) % mod;
    }
}
void inc (ll v, ll val) {
    mul[v] = (mul[v] * val) % mod;
    t[v] = (t[v] * val) % mod;
    dp[v] = (dp[v] * val) % mod;
}
void push (ll v) {
    if (mul[v] != 1) {
        inc(2 * v, mul[v]), inc(2 * v + 1, mul[v]);
        mul[v] = 1;
    }
}
void update (ll l, ll r, ll v = 1, ll left = 0, ll right = m) {
    if (l > r or left > r or l > right) return;
    if (left >= l and right <= r) inc(v, 2);
    else {
        push(v);
        ll mid = (left + right) / 2;
        update(l, r, 2 * v, left, mid), update(l, r, v * 2 + 1, mid + 1, right);
        t[v] = (t[2 * v] + t[2 * v + 1]) % mod;
        dp[v] = (dp[2 * v] + dp[2 * v + 1]) % mod;
    }
}
ll get (ll l, ll r, ll v = 1, ll left = 0, ll right = m) {
    if (l > r or left > r or l > right) return 0;
    if (left >= l and right <= r) return t[v];
    push(v);
    ll mid = (left + right) / 2;
    return (get(l, r, 2 * v, left, mid) + get(l, r, 2 * v + 1, mid + 1, right)) % mod;
}
void update2 (ll pos, ll val, ll v = 1, ll left = 0, ll right = m) {
    if (left == right) {
        if (val == -1) dp[v] = t[v] = 0;
        else {
            dp[v] += val; dp[v] %= mod;
            t[v] = (dp[v] * f[v]) % mod;
        }
    } else {
        push(v);
        ll mid = (left + right) / 2;
        if (pos <= mid) update2(pos, val, 2 * v, left, mid);
        else update2(pos, val, 2 * v + 1, mid + 1, right);
        t[v] = (t[2 * v] + t[2 * v + 1]) % mod;
        dp[v] = (dp[2 * v] + dp[2 * v + 1]) % mod;
    }
}
ll get2 (ll l, ll r, ll v = 1, ll left = 0, ll right = m) {
    if (l > r or left > r or l > right) return 0;
    if (left >= l and right <= r) return dp[v];
    push(v);
    ll mid = (left + right) / 2;
    return (get2(l, r, v * 2, left, mid) + get2(l, r, 2 * v + 1, mid + 1, right)) % mod;
}
void fun (bool flag) {
    vector<ll> d(m + 1);
    d[0] = 1;
    build();
    update2(0, 1);
    ll it = 0;
    for (ll i = 1; i <= n; i++) {
        ll one = get2(0, a2[i] - 1), two = get2(0, b2[i] - 1);
        while (it < a2[i]) update2(it, -1), it++;
        update(b2[i], m), update2(a2[i], one), update2(b2[i], two);
        res += (t[1] * st[n - i]) % mod; res %= mod;
    }
    if (flag) {
        res -= (t[1] * n) % mod;
        if (res < 0) res += mod;
    }
}
void solve () {
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= n; i++) {
        cin >> b[i];
        if (a[i] > b[i]) swap(a[i], b[i]);
    }
    precalc();
    fun(1), rev(), fun(0);
    ll v = 1, sum = 0;
    for (ll i = 1; i <= n; i++) {
        sum += a[i], sum += b[i], sum %= mod;
        if (i < n) v *= 2, v %= mod;
    }
    v = (v * sum) % mod;
    cout << (res - v + mod) % mod;
}

int main() {
    //freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while (t--) solve();
}

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