Submission #1096260

#TimeUsernameProblemLanguageResultExecution timeMemory
1096260epicci23Flooding Wall (BOI24_wall)C++17
0 / 100
4 ms4368 KiB
#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int MOD = 1000000007;
const int N = 5e5 + 5;
const int INV = 5e8 + 4;

inline int add(int a,int b){
 if(a+b>=MOD) return a+b-MOD;
 return a+b;
}

inline int eks(int a,int b){
  if(a>=b) return a-b;
  return a-b+MOD;
}

inline int mult(int a,int b){
  if(a*b>=MOD) return a*b%MOD;
  return a*b;
}

int Pw[N];

struct SegT{
  int n;
  vector<int> lazy,sum,acik;
  SegT(int _n){
    n=_n;
    lazy.assign(4*n+5,1);
    sum.assign(4*n+5,0);
    acik.assign(n+5,0);
  }

  void push(int rt,int l,int r){
    if(lazy[rt]==1 || (l==r && !acik[l])) return;
    sum[rt]=mult(sum[rt],lazy[rt]);
  	int u=lazy[rt];
  	lazy[rt]=1;
    lazy[rt*2]=mult(lazy[rt*2],u);
    lazy[rt*2+1]=mult(lazy[rt*2+1],u);
  }

  void set(int rt,int l,int r,int ind,int u){
  	push(rt,l,r);
    if(r<ind || l>ind) return;
    if(l==r){
      //cout << "setledim: " << ind << '\n';
      //cout << lazy[rt] << ' ' << u << '\n';
      acik[l]=1;
      sum[rt]=mult(lazy[rt],u);
      lazy[rt]=1;
      return;
    }
    int m=(l+r)/2;
    set(rt*2,l,m,ind,u),set(rt*2+1,m+1,r,ind,u);
    sum[rt]=add(sum[rt*2],sum[rt*2+1]);
  }

  void update(int rt,int l,int r,int gl,int gr,int c){
  	if(gl>gr) return;
  	push(rt,l,r);
    if(r<gl || l>gr) return;
    if(l>=gl && r<=gr){
      lazy[rt]=mult(lazy[rt],c);
      push(rt,l,r);
      return;
    }
    int m=(l+r)/2;
    update(rt*2,l,m,gl,gr,c),update(rt*2+1,m+1,r,gl,gr,c);
    sum[rt]=add(sum[rt*2],sum[rt*2+1]);
  }

  int query(int rt,int l,int r,int ind){
  	push(rt,l,r);
  	if(r<ind || l>ind) return -1;
  	if(l==r) return sum[rt];
  	int m=(l+r)/2;
  	int lmao;
  	if(ind<=m) lmao=query(rt*2,l,m,ind);
  	else lmao=query(rt*2+1,m+1,r,ind);
  	sum[rt]=add(sum[rt*2],sum[rt*2+1]);
  	return lmao;
  }
};

void _(){
  int n;cin >> n;
  int ar[n+5][2];
  for(int i=1;i<=n;i++) cin >> ar[i][0];
  for(int i=1;i<=n;i++) cin >> ar[i][1];
  
  int ans=0;
  for(int i=1;i<=n;i++) ans=eks(ans,mult(Pw[n-1],ar[i][0]));
  for(int i=1;i<=n;i++) ans=eks(ans,mult(Pw[n-1],ar[i][1]));

  map<int,vector<int>> mp;
  for(int i=1;i<=n;i++)
  	for(int j=0;j<2;j++)
  	  mp[-ar[i][j]].push_back(i);

  SegT R(n+5);
  vector<int> T(n+5,0);
  
  for(int i=2;i<=n;i++) R.update(1,1,n,1,i-1,2);
  for(auto x:mp){
    for(int& i:x.second){
      T[i]++;
      if(T[i]==1){
        R.set(1,1,n,i,mult(i,Pw[i-1]));
        R.update(1,1,n,1,i-1,INV);
      }
      else{
        R.update(1,1,n,i,i,2);
        R.update(1,1,n,1,i-1,0);
      }
    }
    ans=add(ans,R.sum[1]);
  }
  
  SegT L(n+5);
  T.assign(n+5,0);
  for(int i=0;i<n;i++) L.update(1,0,n-1,i+1,n-1,2);
  for(auto x:mp){
    for(int& i:x.second){
      i--;
      T[i]++;
      if(T[i]==1){
        L.set(1,0,n-1,i,mult(i,Pw[n-1-i]));
        L.update(1,0,n-1,i+1,n-1,INV);
      }
      else{
        L.update(1,0,n-1,i,i,2);
        L.update(1,0,n-1,i+1,n-1,0);
      }
    }
    ans=eks(ans,L.sum[1]);
  }

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  Pw[0]=1;
  for(int i=1;i<N;i++) Pw[i]=add(Pw[i-1],Pw[i-1]);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...