Submission #1361262

#TimeUsernameProblemLanguageResultExecution timeMemory
1361262NewtonabcFlooding Wall (BOI24_wall)C++20
100 / 100
852 ms103348 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const int M=1<<21;
const ll MOD=1e9+7;
ll t[N][2],arr[N];
ll po[N],il[N],ir[N];
int n;
vector<ll> h;
vector<int> pos[N];
struct node{
    ll spl,spr,prd;
    friend node operator+(const node &x,const node &y){
        if(x.spl==LLONG_MIN) return y;
        if(y.spl==LLONG_MIN) return x;
        node ret;
        ret.spl=(x.spl+(y.spl*x.prd))%MOD;
        ret.spr=(y.spr+(x.spr*y.prd))%MOD;
        ret.prd=(x.prd*y.prd)%MOD;
        return ret;
    }
    ll flex(){
        ll tmp=(spl+spr-(ll)n*prd)%MOD;
        if(tmp<0) tmp+=MOD;
        return tmp;
    }
}s[M];
void update(int l,int r,int idx,int a){
    if(a>r || a<l) return;
    if(l==r){
        s[idx]={(po[n-l]*arr[l])%MOD,(po[l-1]*arr[l])%MOD,arr[l]};
        return;
    }
    int m=(l+r)/2;
    update(l,m,idx*2,a);
    update(m+1,r,idx*2+1,a);
    s[idx]=s[idx*2]+s[idx*2+1];
}
node query(int l,int r,int idx,int a,int b){
    if(a>r || b<l) return {LLONG_MIN,0,0};
    if(a<=l && b>=r) return s[idx];
    int m=(l+r)/2;
    return query(l,m,idx*2,a,b)+query(m+1,r,idx*2+1,a,b);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    ll sum=0;
    po[0]=1;
    for(int i=1;i<=n;i++) po[i]=(po[i-1]*2LL)%MOD;
    for(int i=1;i<=n;i++) cin>>t[i][0],h.push_back(t[i][0]),sum+=t[i][0],sum%=MOD;
    for(int i=1;i<=n;i++) cin>>t[i][1],h.push_back(t[i][1]),sum+=t[i][1],sum%=MOD;
    sort(h.begin(),h.end());
    h.erase(unique(h.begin(),h.end()),h.end());
    for(int i=1;i<=n;i++){
        int id=lower_bound(h.begin(),h.end(),t[i][0])-h.begin();
        pos[id].push_back(i);
        id=lower_bound(h.begin(),h.end(),t[i][1])-h.begin();
        pos[id].push_back(i);
    }
    int sz=h.size();
    ll mxh=h[(int)h.size()-1];
    ll ret=(mxh*po[n])%MOD;
    ret=(ret*n)%MOD;
    //cout<<ret <<" ";
    ret-=(sum*po[n-1])%MOD;
    //cout<<ret <<"\n";
    ret=((ret%MOD)+MOD)%MOD;
    for(int i=0;i<sz;i++){
        //calculate
        node got=query(1,n,1,1,n);
        ll out=got.flex();
        out=(out*(h[i]-(i==0?0:h[i-1])))%MOD;
        ret=(((ret-out)%MOD)+MOD)%MOD;
        //for(int i=1;i<=n;i++) cout<<arr[i] <<" ";
        //cout<<"\n";
        //cout<<got.spl <<" " <<got.spr <<" " <<got.prd <<"\n";
        //add the value == h[i]
        for(auto x:pos[i]){
            arr[x]++;
            update(1,n,1,x);
        }
    }
    cout<<ret;
}
#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...