Submission #1063137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063137		shenfe1	Flooding Wall (BOI24_wall)	C++17	100 / 100	2886 ms	123952 KiB

Main

#include <bits/stdc++.h>
    
#pragma GCC optimize("Ofast")
    
using namespace std;
    
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define int ll

const int MAX=1e6+10;
const int mod=1e9+7;

int n;
int a[MAX],b[MAX];
vector<int> vec;

struct segtree{
    int t[4*MAX],t1[4*MAX],add[4*MAX];

    void init(int n){
        for(int i=1;i<=4*n;i++){
            t[i]=t1[i]=0;
            add[i]=1;
        }
    }

    void upd(int v,int x){
        t[v]=t[v]*x%mod;
        t1[v]=t1[v]*x%mod;
        add[v]=add[v]*x%mod;
    }

    void push(int v){
        if(add[v]!=1){
            upd(2*v,add[v]);
            upd(2*v+1,add[v]);
            add[v]=1;
        }
    }

    void update(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            upd(v,x);
            return;
        }
        push(v);
        int tm=(tl+tr)/2;
        update(2*v,tl,tm,l,r,x);
        update(2*v+1,tm+1,tr,l,r,x);
        t[v]=(t[2*v]+t[2*v+1])%mod;
        t1[v]=(t1[2*v]+t1[2*v+1])%mod;
    }

    void set(int v,int tl,int tr,int pos,int x){
        if(tl==tr){
            t[v]=x;
            t1[v]=vec[tl]*x%mod;
            return;
        }
        push(v);
        int tm=(tl+tr)/2;
        if(pos<=tm)set(2*v,tl,tm,pos,x);
        else set(2*v+1,tm+1,tr,pos,x);
        t[v]=(t[2*v]+t[2*v+1])%mod;
        t1[v]=(t1[2*v]+t1[2*v+1])%mod;
    }

    int get(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return 0;
        if(l<=tl&&tr<=r)return t[v];
        push(v);
        int tm=(tl+tr)/2;
        return (get(2*v,tl,tm,l,r)+get(2*v+1,tm+1,tr,l,r))%mod;
    }

    int getT(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return 0;
        if(l<=tl&&tr<=r)return t1[v];
        push(v);
        int tm=(tl+tr)/2;
        return (getT(2*v,tl,tm,l,r)+getT(2*v+1,tm+1,tr,l,r))%mod;
    }
}T;

int pw[MAX];

void solve(){
    cin>>n;
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=(pw[i-1]*2)%mod;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    vec.pb(0);
    for(int i=1;i<=n;i++)vec.pb(a[i]),vec.pb(b[i]);
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    for(int i=1;i<=n;i++){
        a[i]=lb(all(vec),a[i])-vec.begin();
        b[i]=lb(all(vec),b[i])-vec.begin();
        if(a[i]>b[i])swap(a[i],b[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans-=(vec[a[i]]+vec[b[i]])*pw[n-1]%mod;
        if(ans<0)ans+=mod;
    }
    T.init(2*n+1);
    T.set(1,0,2*n,0,1);
    for(int i=1;i<=n;i++){
        int x=T.get(1,0,2*n,0,a[i]);
        int y=(T.get(1,0,2*n,0,b[i])+T.get(1,0,2*n,b[i],b[i]))%mod;
        T.set(1,0,2*n,a[i],x);
        T.set(1,0,2*n,b[i],y);
        T.update(1,0,2*n,0,a[i]-1,0);
        T.update(1,0,2*n,b[i]+1,2*n,2);
        ans+=T.getT(1,0,2*n,0,2*n)*pw[n-i]%mod;
        if(ans>=mod)ans-=mod;
    }
    ans-=T.getT(1,0,2*n,0,2*n)*n%mod;
    if(ans<0)ans+=mod;
    T.init(2*n+1);
    T.set(1,0,2*n,0,1);
    for(int i=n;i>=1;i--){
        int x=T.get(1,0,2*n,0,a[i]);
        int y=(T.get(1,0,2*n,0,b[i])+T.get(1,0,2*n,b[i],b[i]))%mod;
        T.set(1,0,2*n,a[i],x);
        T.set(1,0,2*n,b[i],y);
        T.update(1,0,2*n,0,a[i]-1,0);
        T.update(1,0,2*n,b[i]+1,2*n,2);
        ans+=T.getT(1,0,2*n,0,2*n)*pw[i-1]%mod;
        if(ans>=mod)ans-=mod;    
    }
    cout<<ans<<"\n";
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
}

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