Submission #1098974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098974		_8_8_	Flooding Wall (BOI24_wall)	C++17	58 / 100	1877 ms	2376 KiB

Main

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

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

int n, a[N], b[N], m, ai[N], bi[N];

ll t[4 * N], mul[N * 4], 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 slow() {
    ll ret = 0;
    for(int i = 0; i < (1 << n); i++) {
        int mx = 0;
        for(int j = 0; j < n; j++) {
            if((i >> j) & 1) {
                mx = max(mx, a[j + 1]);
            } else {
                mx = max(mx, b[j + 1]);
            }
        }
        ret += mx * n;
    }
    return ret;
}
void solve(bool fi = true) {
    vector<ll> d(m + 1, 0);
    d[0] = 1;
    for(int i = 1; i <= n; i++) {
        ll s = 0, _s = 0;
        for(int j = 0; j < bi[i]; j++) {
            add(_s, d[j]);
            if(j < ai[i]) {
                add(s, d[j]);
            }
        }
        for(int j = 0; j < ai[i]; j++) {
            d[j] = 0;
        }
        for(int j = bi[i]; j <= m; j++) {
            add(d[j], d[j]);
        }
        add(d[ai[i]], s);
        add(d[bi[i]], _s);
        for(int j = 1; j <= m; j++) {
            add(res, d[j] * c[j - 1] % MOD * st[n - i] % MOD);
        }
    }
    if(fi) {
        ll K = 0;
        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';
}
int 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:84:12: warning: unused variable 'K' [-Wunused-variable]
   84 |         ll K = 0;
      |            ^

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