Submission #1006292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006292		hmm789	Flooding Wall (BOI24_wall)	C++14	100 / 100	3383 ms	248760 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define MOD 1000000007
#define HALF 500000004
#define INF 1000000000000000000

int p2[500005], ph[500005];

struct node {
    int s, e, m, sum, mul[3];
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, sum = 0, mul[0] = mul[1] = mul[2] = 0;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void rmul(int x, int y, int val) {
        if(x > y) return;
        if(x <= s && e <= y) {
            if(val == -1) mul[0]--;
            else mul[val]++;
            return;
        } else if(x > m) r->rmul(x, y, val);
        else if(y <= m) l->rmul(x, y, val);
        else l->rmul(x, y, val), r->rmul(x, y, val);
        sum = (l->get() + r->get()) % MOD;
    }
    void setsum(int x, int val) {
        if(s == e) {sum = val; return;}
        else if(x > m) r->setsum(x, val);
        else l->setsum(x, val);
        sum = (l->get() + r->get()) % MOD;
    }
    int get() {
        int ans = sum;
        if(mul[0]) return 0;
        ans = ans * ph[mul[1]] % MOD;
        ans = ans * p2[mul[2]] % MOD;
        return ans;
    }
} *rt, *lt;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    p2[0] = ph[0] = 1;
    for(int i = 1; i < 500005; i++) p2[i] = p2[i-1] * 2 % MOD;
    for(int i = 1; i < 500005; i++) ph[i] = ph[i-1] * HALF % MOD;
    int n, ans = 0;
    cin >> n;
    int a[n+1], b[n+1], cnt[n+1];
    memset(cnt, 0, sizeof(cnt));
    vector<int> dis, vec[2*n+1];
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) {
        dis.push_back(a[i]);
        dis.push_back(b[i]);
        ans = (ans - (a[i]+b[i]) * p2[n-1] % MOD + MOD) % MOD;
    }
    dis.push_back(0);
    sort(dis.begin(), dis.end());
    dis.erase(unique(dis.begin(), dis.end()), dis.end());
    for(int i = 1; i <= n; i++) {
        vec[lower_bound(dis.begin(), dis.end(), a[i])-dis.begin()].push_back(i);
        vec[lower_bound(dis.begin(), dis.end(), b[i])-dis.begin()].push_back(i);
    }
    rt = new node(1, n);
    lt = new node(1, n);
    for(int i = 1; i <= n; i++) {
        rt->setsum(i, i*p2[n-1] % MOD);
        rt->rmul(i, i, 0);
        lt->setsum(i, (i-1)*p2[n-1] % MOD);
        lt->rmul(i, i, 0);
    }
    for(int i = dis.size()-1; i; i--) {
        for(int it : vec[i]) {
            cnt[it]++;
            if(cnt[it] == 1) {
                rt->rmul(it, it, -1);
                rt->rmul(1, it-1, 1);
                lt->rmul(it, it, -1);
                lt->rmul(it+1, n, 1);
            } else {
                rt->rmul(it, it, 2);
                rt->rmul(1, it-1, 0);
                lt->rmul(it, it, 2);
                lt->rmul(it+1, n, 0);
            }
        }
        ans += (rt->get() - lt->get() + MOD) % MOD * (dis[i]-dis[i-1]) % MOD;
        ans %= MOD;
    }
    cout << ans;
}

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