Submission #1132010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132010		vladilius	Flooding Wall (BOI24_wall)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int mod = 1e9 + 7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    vector<int> b(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>b[i];
    }
    
    vector<int> tw(n + 1); tw[0] = 1;
    for (int i = 1; i < n; i++) tw[i] = (2 * tw[i - 1]) % mod;
    
    for (int i = 1; i <= n; i++){
        if (a[i] > b[i]){
            swap(a[i], b[i]);
        }
    }
    
    ll out = 0;
    for (int i = 1; i <= n; i++){
        out = (out - 1LL * tw[n - 1] * (a[i] + b[i])) % mod;
    }
    
    vector<pii> f;
    for (int i = 1; i <= n; i++){
        f.pb({a[i], i});
        f.pb({b[i], -i});
    }
    sort(f.begin(), f.end());
    int i = 0, m = 0;
    while (i < f.size()){
        int j = i; m++;
        while (j < f.size() && f[i].ff == f[j].ff){
            int t = f[j].ss;
            if (t > 0) a[t] = m;
            else b[-t] = m;
            j++;
        }
        i = j;
    }
    
    vector<vector<int>> mx(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++){
        for (int j = i; j <= n; j++){
            mx[i][j] = max(mx[i][j - 1], a[j]);
        }
    }
    
    vector<vector<int>> p(m + 1, vector<int>(n + 1));
    for (int x = 1; x <= m; x++){
        for (int i = 1; i <= n; i++){
            p[x][i] = p[x][i - 1] + (b[i] <= x);
        }
    }
    
    auto get1 = [&](int l, int r, int x){
        if (l <= r && mx[l][r] > x) return 0;
        return tw[p[x][r] - p[x][l - 1]];
    };
    
    auto get2 = [&](int l, int r, int x){
        return tw[r - l + 1] - get1(l, r, x - 1);
    };
    
    vector<int> all1;
    for (int i = 1; i <= n; i++){
        all1.pb(a[i]);
        all1.pb(b[i]);
    }
    sort(all1.begin(), all1.end());
    vector<int> all;
    for (int j = 0; j < all1.size(); j++){
        if (!j || all1[j - 1] != all1[j]){
            all.pb(all1[j]);
        }
    }

    for (int i = 1; i <= n; i++){
        for (int j: all){
            if (a[i] == j){
                out += ((1LL * j * get1(1, i - 1, j)) % mod * tw[n - i]) % mod;
                out += (((j * get1(i + 1, n, j)) % mod) * get2(1, i - 1, j + 1)) % mod;
            }
            else if (a[i] < j){
                out += (((j * (get1(1, i - 1, j) - get1(1, i - 1, j - 1))) % mod) * get2(i + 1, n, j)) % mod;
                out += (((j * (get1(i + 1, n, j) - get1(i + 1, n, j - 1))) % mod) * get2(1, i - 1, j + 1)) % mod;
            }
            
            if (b[i] == j){
                out += ((1LL * j * get1(1, i - 1, j)) % mod * tw[n - i]) % mod;
                out += (((j * get1(i + 1, n, j)) % mod) * get2(1, i - 1, j + 1)) % mod;
            }
            else if (b[i] < j){
                out += (((j * (get1(1, i - 1, j) - get1(1, i - 1, j - 1))) % mod) * get2(i + 1, n, j)) % mod;
                out += (((j * (get1(i + 1, n, j) - get1(i + 1, n, j - 1))) % mod) * get2(1, i - 1, j + 1)) % mod;
            }
        }
        out %= mod;
    }
    
    if (out < 0) out += mod;
    cout<<out<<"\n";
}

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