제출 #1276180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276180		vibeduck	Flooding Wall (BOI24_wall)	C++20	0 / 100	5097 ms	35664 KiB

Main

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

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

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

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

    int n; 
    cin >> n;
    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;

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

    long long ans = 0;

    for(int m : levels){
        // ge[i] = # of choices >= m at i; lt[i] = # of choices < 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 lt==0 and lt==2 so we can query any interval fast
        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

                // middles are indices (j+1 .. i-1)
                int zeroCnt = prefZero[i] - prefZero[j+1];
                if(zeroCnt>0) continue; // some middle has no <m option -> impossible

                int cnt2 = prefTwo[i] - prefTwo[j+1]; // middles with both < m

                long long ways = 1;
                ways = mulm(ways, ge[j]);           // choose >= m at j
                ways = mulm(ways, ge[i]);           // choose >= m at i
                ways = mulm(ways, pw2[cnt2]);       // middles with both < m
                ways = mulm(ways, pw2[j]);          // free left side
                ways = mulm(ways, pw2[n-1-i]);      // free right side

                long long contrib = mulm(i - j - 1, ways);
                ans = addm(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