Submission #1356691

#TimeUsernameProblemLanguageResultExecution timeMemory
1356691AvianshFlooding Wall (BOI24_wall)C++20
25 / 100
5091 ms1984 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9+7;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int a[n],b[n];
    for(int &i : a){
        cin >> i;
    }
    for(int &i : b){
        cin >> i;
    }
    long long po[n];
    po[0]=1;
    for(int i = 1;i<n;i++){
        po[i]=po[i-1]*2;
        po[i]%=mod;
    }
    for(int i = 0;i<n;i++){
        if(a[i]>b[i])
            swap(a[i],b[i]);
    }
    vector<array<int,2>>pts(2*n);
    for(int i = 0;i<n;i++){
        pts[i]={a[i],i};
        pts[i+n]={b[i],i};
    }
    long long ans = 0;
    sort(pts.begin(),pts.end());
    for(int i = 1;i<n-1;i++){
        vector<array<int,2>>lef;
        vector<array<int,2>>rig;
        for(array<int,2>pt:pts){
            if(pt[1]<i){
                lef.push_back(pt);
            }
            if(pt[1]>i){
                rig.push_back(pt);
            }
        }
        vector<array<int,2>>lefcnt,rigcnt;
        ///each stores cnt like so: {mxval in segment, num ways}
        bool vis[n];
        fill(vis,vis+n,0);
        int cnvis = 0;
        int mult = 0;
        for(array<int,2> a : lef){
            bool curr = 0;
            if(!vis[a[1]]){
                vis[a[1]]=1;
                cnvis++;
            }
            else {
                mult++;
                curr=1;
            }
            if(cnvis!=i){
                continue;
            }
            ///now this is actually doable
            lefcnt.push_back({a[0],po[mult-curr]});
        }

        cnvis = 0;
        mult = 0;
        for(array<int,2> a : rig){
            bool curr = 0;
            if(!vis[a[1]]){
                vis[a[1]]=1;
                cnvis++;
            }
            else {
                mult++;
                curr=1;
            }
            if(cnvis!=n-i-1){
                continue;
            }
            ///now this is actually doable
            rigcnt.push_back({a[0],po[mult-curr]});
        }

        for(array<int,2> l:lefcnt){
            for(array<int,2>r:rigcnt){
                if(min(l[0],r[0])>a[i]){
                    ans+=(min(l[0],r[0])-a[i])*((l[1]*r[1])%mod);
                    ans%=mod;
                }
                if(min(l[0],r[0])>b[i]){
                    ans+=(min(l[0],r[0])-b[i])*((l[1]*r[1])%mod);
                    ans%=mod;
                }
            }
        }
    }
    cout << ans;
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...