Submission #1276170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276170		vibeduck	Flooding Wall (BOI24_wall)	C++20	0 / 100	5096 ms	35668 KiB

Main

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

#define int long long
const int MOD = 1e9 + 7;

int addmod(int a,int b){ a+=b; if(a>=MOD) a-=MOD; return a; }
int mulmod(long long a,long long b){ return (a%MOD)*(b%MOD)%MOD; }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if(!(cin>>n)) return 0;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];

    // powers of two
    vector<int> pw2(n+5,1);
    for(int i=1;i<(int)pw2.size();i++) pw2[i] = (pw2[i-1]*2)%MOD;

    // all distinct candidate levels m
    vector<int> vals;
    vals.reserve(2*n);
    for(int i=0;i<n;i++){ vals.push_back(a[i]); vals.push_back(b[i]); }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    long long ans = 0;

    for(int m : vals){
        // ge[i] = #options at i that are >= m; lt[i] = #options < m
        vector<int> ge(n), lt(n);
        for(int i=0;i<n;i++){
            ge[i] = (a[i]>=m) + (b[i]>=m);
            lt[i] = (a[i]<m) + (b[i]<m);
        }
        // prefix counts of zeros and twos in lt
        vector<int> prefZero(n+1,0), prefTwo(n+1,0);
        for(int i=0;i<n;i++){
            prefZero[i+1] = prefZero[i] + (lt[i]==0);
            prefTwo[i+1]  = prefTwo[i]  + (lt[i]==2);
        }

        for(int i=1;i<n;i++){
            if(ge[i]==0) continue;                    // right endpoint can't be a wall at level m
            for(int j=i-1;j>=0;j--){
                if(ge[j]==0) continue;                // left endpoint can't be a wall at level m
                // middle indices (j+1 .. i-1)
                if(prefZero[i] - prefZero[j+1] > 0)   // some middle has no <m option -> impossible
                    continue;

                int cnt2 = prefTwo[i] - prefTwo[j+1]; // middles with both < m
                long long ways = 1;
                ways = mulmod(ways, ge[j]);           // choose >=m at j
                ways = mulmod(ways, ge[i]);           // choose >=m at i
                ways = mulmod(ways, pw2[cnt2]);       // middles product = 2^{#both< m}
                ways = mulmod(ways, pw2[j]);          // free left side
                ways = mulmod(ways, pw2[n-1-i]);      // free right side

                long long contrib = mulmod((i - j - 1), ways);
                ans = addmod(ans, contrib);
            }
        }
    }

    cout << (ans % MOD) << '\n';
    return 0;
}

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