Submission #1356702

#TimeUsernameProblemLanguageResultExecution timeMemory
1356702AvianshFlooding Wall (BOI24_wall)C++20
0 / 100
0 ms348 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]});
        }
        vector<array<int,2>>lefcntsuf,rigcntsuf;
        for(array<int,2>a:lefcnt){
            if(lefcntsuf.size()){
                if(lefcntsuf.back()[0]==a[0]){
                    lefcntsuf.back()[1]+=a[1];
                    continue;
                }
            }
            lefcntsuf.push_back(a);
        }
        for(array<int,2>a:rigcnt){
            if(rigcntsuf.size()){
                if(rigcntsuf.back()[0]==a[0]){
                    rigcntsuf.back()[1]+=a[1];
                    continue;
                }
            }
            rigcntsuf.push_back(a);
        }
        for(int i = lefcntsuf.size()-2;i>=0;i--){
            lefcntsuf[i][1]+=lefcntsuf[i+1][1];
            lefcntsuf[i][1]%=mod;
        }
        for(int i = rigcntsuf.size()-2;i>=0;i--){
            rigcntsuf[i][1]+=rigcntsuf[i+1][1];
            rigcntsuf[i][1]%=mod;
        }
        for(array<int,2> l : lefcnt){
            ///l[0]<r[0]
            auto it = lower_bound(rigcntsuf.begin(),rigcntsuf.end(),(array<int,2>){l[0]+1,-1});
            if(it==rigcntsuf.end())
                continue;
            if(l[0]>a[i]){
                ans+=(l[0]-a[i])*((l[1]*(*it)[1])%mod);
            }
            if(l[0]>b[i]){
                ans+=(l[0]-b[i])*((l[1]*(*it)[1])%mod);
            }
        }
        for(array<int,2> r : rigcnt){
            ///r[0]<=l[0]
            auto it = lower_bound(lefcntsuf.begin(),lefcntsuf.end(),(array<int,2>){r[0],-1});
            if(it==lefcntsuf.end())
                continue;
            if(r[0]>a[i]){
                ans+=(r[0]-a[i])*((r[1]*(*it)[1])%mod);
            }
            if(r[0]>b[i]){
                ans+=(r[0]-b[i])*((r[1]*(*it)[1])%mod);
            }
        }
        /*
        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...