제출 #1132020

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132020		vladilius	Flooding Wall (BOI24_wall)	C++20	70 / 100	2669 ms	1114112 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());
    vector<int> act = {0};
    int i = 0, m = 0;
    while (i < f.size()){
        int j = i; m++;
        act.pb(f[i].ff);
        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<int> log(n + 1);
    for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
    const int lg = log[n];
    vector<vector<int>> sp(n + 1, vector<int>(lg + 1));
    for (int i = 1; i <= n; i++) sp[i][0] = a[i];
    for (int j = 1; j <= lg; j++){
        for (int i = 1; i + (1 << j) <= n + 1; i++){
            sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
    
    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) return 1;
        int k = log[r - l + 1];
        if (max(sp[l][k], sp[r - (1 << k) + 1][k]) > 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 * act[j] * get1(1, i - 1, j)) % mod * tw[n - i]) % mod;
                out += (((1LL * act[j] * get1(i + 1, n, j)) % mod) * get2(1, i - 1, j + 1)) % mod;
            }
            else if (a[i] < j){
                out += (((1LL * act[j] * (get1(1, i - 1, j) - get1(1, i - 1, j - 1))) % mod) * get2(i + 1, n, j)) % mod;
                out += (((1LL * act[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 * act[j] * get1(1, i - 1, j)) % mod * tw[n - i]) % mod;
                out += (((1LL * act[j] * get1(i + 1, n, j)) % mod) * get2(1, i - 1, j + 1)) % mod;
            }
            else if (b[i] < j){
                out += (((1LL * act[j] * (get1(1, i - 1, j) - get1(1, i - 1, j - 1))) % mod) * get2(i + 1, n, j)) % mod;
                out += (((1LL * act[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: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30