Submission #1014033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014033		hengliao	Flooding Wall (BOI24_wall)	C++17	58 / 100	5046 ms	38792 KiB

Main

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mod=1e9+7;
const ll mxN=5e5+5;

ll pw(ll a, ll b){
    ll re=1;
    for(ll i=0;i<63;i++){
        if(b&(1LL<<i)){
            re*=a;
            re%=mod;
        }
        a*=a;
        a%=mod;
    }
    return re;
}

ll inv(ll a){
    return pw(a, mod-2);
}

ll seg[mxN];
ll lef[mxN][2];
ll rig[mxN][2];
bool good[mxN][2];
ll n;
ll a[mxN][2];
vector<pair<ll, pll>> v;

bool compare(pair<ll, pll> &a, pair<ll, pll> &b){
    if(a.F!=b.F){
        return a.F>b.F;
    }
    return a.S.F<b.S.F;
}

bool compare2(pair<ll, pll> &a, pair<ll, pll> &b){
    if(a.F!=b.F){
        return a.F>b.F;
    }
    return a.S.F>b.S.F;
}

void solve(){
    memset(good, 0, sizeof(good));
	cin>>n;
    for(ll i=0;i<n;i++){
        cin>>a[i][0];
    }
    for(ll i=0;i<n;i++){
        cin>>a[i][1];
    }
    for(ll i=0;i<n;i++){
        v.pb({a[i][0], {i, 0}});
        v.pb({a[i][1], {i, 1}});
        seg[i]=2;
    }
    sort(v.begin(), v.end(), compare);
    ll ans=0;
    for(auto &it:v){
        ll val=it.F;
        ll id=it.S.F;
        ll id2=it.S.S;
        ll pre=1;
        ll cur=0;
        for(ll i=id-1;i>=0;i--){
            for(ll j=0;j<2;j++){
                if(good[i][j]){
                    cur+=(((id-i)*pre)%mod)*lef[i][j];
                    cur%=mod;
                }
            }   
            pre*=seg[i];
            pre%=mod;
        }
        ll pre2=1;
        for(ll i=id+1;i<n;i++){
            pre2*=seg[i];
            pre2%=mod;
        }
        ans+=((cur*pre2)%mod)*val;
        //cout<<"dealing with "<<val<<' '<<id<<' '<<id2<<'\n';
        //cout<<((cur*pre2))*val<<' ';
        ans%=mod;
        //calculate lef
        lef[id][id2]=1;
        for(ll i=0;i<id;i++){
            lef[id][id2]*=seg[i];
            lef[id][id2]%=mod;
        }
        ans+=((val*lef[id][id2])%mod)*pre2;
        //cout<<((val*lef[id][id2]))*pre2<<'\n';
		lef[id][id2]=pw(2, id);
        ans%=mod;
        good[id][id2]=1;
        seg[id]--;
    }
    //cout<<ans<<'\n';
    sort(v.begin(), v.end(), compare2);
    memset(good, 0, sizeof(good));
    for(ll i=0;i<n;i++){
        seg[i]=2;
    }
    for(auto &it:v){
        ll val=it.F;
        ll id=it.S.F;
        ll id2=it.S.S;
        ll pre=1;
        ll cur=0;
        for(ll i=id+1;i<n;i++){
            for(ll j=0;j<2;j++){
                if(good[i][j]){
                    cur+=(((i-id)*pre)%mod)*rig[i][j];
                    cur%=mod;
                }
            }   
            pre*=seg[i];
            pre%=mod;
        }
        ll pre2=1;
        for(ll i=id-1;i>=0;i--){
            pre2*=seg[i];
            pre2%=mod;
        }
        ans+=((cur*pre2)%mod)*val;
        //cout<<"dealing with "<<val<<' '<<id<<' '<<id2<<'\n';
        //cout<<((cur*pre2))*val<<'\n';
        ans%=mod;
        //calculate rig
        rig[id][id2]=pw(2, n-id-1);
        /*ans+=((val*rig[id][id2])%mod)*pre2;
        ans%=mod;*/
        good[id][id2]=1;
        seg[id]--;
    }
    //cout<<ans<<'\n';
    memset(good, 0, sizeof(good));
    for(ll i=0;i<n;i++){
        seg[i]=2;
    }
    for(auto &it:v){
        ll val=it.F;
        ll id=it.S.F;
        ll id2=it.S.S;
        ll pre=1;
        ll cur=0;
        for(ll i=id+1;i<n;i++){
            for(ll j=0;j<2;j++){
                if(good[i][j] && a[i][j]==val){
                    cur+=(((i-id)*pre)%mod)*rig[i][j];
                    cur%=mod;
                }
            }   
            pre*=seg[i];
            pre%=mod;
        }
        ll pre2=1;
        for(ll i=id-1;i>=0;i--){
            pre2*=seg[i];
            pre2%=mod;
        }
        ans-=((cur*pre2)%mod)*val;
        //cout<<"dealing with "<<val<<' '<<id<<' '<<id2<<'\n';
        //cout<<((cur*pre2))*val<<'\n';
		//cout<<cur<<'\n';
        ans%=mod;
        if(ans<0) ans+=mod;
        //calculate rig
        //rig[id][id2]=pw(2, n-id-1);
		rig[id][id2]=1;
        for(ll i=id+1;i<n;i++){
            if(a[i][0]==val || a[i][1]==val) rig[id][id2]*=(seg[i]+1);
			else rig[id][id2]*=seg[i];
            rig[id][id2]%=mod;
        }
        good[id][id2]=1;
        seg[id]--;
    }
    //cout<<ans<<'\n';
    for(ll i=0;i<n;i++){
        for(ll j=0;j<2;j++){
            ans-=a[i][j]*pw(2, n-1);
            ans%=mod;
            if(ans<0) ans+=mod;
        }
    }
    cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	solve();
	return 0;
}

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