Submission #999470

#	Time	Username	Problem	Language	Result	Execution time	Memory
999470		AlperenT_	Flooding Wall (BOI24_wall)	C++17	100 / 100	3680 ms	179876 KiB

Main

#include <bits/stdc++.h>
 

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 5e5 + 10  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333   , inf = 2e9 +100 , maxk = 2022 , mod = 1e9 + 7 ;
int n , s[28*maxn] , a2   , lz[28*maxn] , a[maxn] , b[maxn] , pr[maxn] , sf[maxn] , ans =0  ;
vector <int> cm ;

int po(int a, int b){
  if(b==0)return 1;
  int v= po(a,b/2);
  v= v*v % mod ;
  if(b&1) v = v*a % mod ;
  return v; 
}

void shi(int p){
  int pl = p<<1 ,pr =p<<1|1;
  s[pl] = s[pl] * lz[p] % mod ;
  s[pr] = s[pr] * lz[p]%mod ;
  lz[pl] = lz[pl] * lz[p] % mod ;
  lz[pr] = lz[pr] * lz[p] % mod ;
  lz[p] = 1; 
}

void bui(int p =1 ,int l = 0 , int r =sz(cm)-2){
  int mid = (l+r)/2 , pl = p<<1 , pr = p<<1|1 ;
  if(l == r){
    s[p] =cm[l+1]-cm[l] ;
    lz[p] =1 ;
    return ;
  }
  bui(pl,l,mid);
  bui(pr,mid+1 , r);
  s[p] = (s[pl] + s[pr])%mod ;
  lz[p] =1 ;
}
void upd(int le ,int ri ,int w ,int p = 1, int l = 0 , int r =sz(cm)-2){
  int mid = (l+r) /2 , pl =p<<1,pr=p<<1|1 ;
  if(le > r || l > ri)return ;
  if(l!=r)shi(p) ;
  if(le <= l && r <= ri){
    s[p] = (s[p] * w)%mod ;
    lz[p] = lz[p] * w % mod ;
    return ;
  }
  upd(le,ri,w,pl,l,mid);
  upd(le,ri,w,pr,mid+1,r) ;
  s[p] = (s[pl] + s[pr])%mod ;
  lz[p] =1 ;
}
int que(int le ,int ri , int p =1 ,int l = 0 , int r =sz(cm)-2){
  int mid = (l+r)/2 , pl = p<<1 ,pr = p<<1|1 ;
  if(le > r || l > ri)return 0 ;
  if(l!=r)shi(p) ;
  if(le <= l &&r <= ri)return s[p] ;
  return (que(le ,ri ,pl,l,mid) + que(le , ri ,pr ,mid+1 , r))%mod ;
}
vector <pair<pii , int> > v1[maxn] , v2[maxn] , v3[maxn] ;

void sl(int i , int l ,int r, int w){
  int x = min(pr[i-1] , sf[i+1]) , y = max(pr[i-1] ,sf[i+1] )+1 ;
  ans = (ans + max(0ll , min(x,r)-l+1) * w)%mod ;
  l = max(l , x+1) ;
  if(l > r)return ;
  y = max(y, l);
  if(r >= y){
    cm.pb(y);cm.pb(r+1) ;
    ans = (ans + (r-y+1)*w)%mod ;
    v3[i].pb({{y,r+1},w});
    v2[i].pb({{y,r+1},(-w+mod)%mod}) ;
    v1[i].pb({{y,r+1},(-w+mod)%mod}) ;
  }
  r = min(r,y-1);
  if(l > r)return ;
  cm.pb(l);cm.pb(r+1);
  ans = (ans + (r-l+1)*w)%mod ;
  if(pr[i-1] > sf[i+1]){
    v2[i].pb({{l,r+1},(-w+mod)%mod});
  }else{
    v1[i].pb({{l,r+1},(-w+mod)%mod});
  }
}
int f(int x){
  int y = lower_bound(all(cm) , x) - cm.begin() ;
  return y ;
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);   
  a2 = po(2, mod-2) ;
  cin >> n ;
  rep(i , 1,n){
    cin >> a[i] ;
  } 
  rep(i , 1 ,n){
    cin >> b[i] ;
    if(a[i] > b[i])swap(a[i] , b[i]) ;
  }
  pr[0] = -inf ;
  rep(i ,1 ,n){
    pr[i] = max(pr[i-1] , a[i]) ;
  }
  sf[n+1] = -inf ;
  per(i , n ,1 ){
    sf[i] = max(sf[i+1] , a[i]) ; 
    cm.pb(a[i]+1);cm.pb(b[i]+1) ;
  }
  rep(i ,2 , n-1){
    sl(i,a[i] + 1, b[i] , a2) ;
    sl(i,b[i] +1 , 1e9 , 1) ; 
  }
  sort(all(cm)) ;
  cm.resize(unique(all(cm)) - cm.begin()) ;
  bui() ;
  rep(i ,1 , n){
    for(auto [x, w] : v1[i]){
      x.F = f(x.F) ;
      x.S = f(x.S) ; 
      ans = (ans + w * que(x.F,x.S-1))%mod ;
    }
    upd(f(a[i]+1) ,f(b[i]+1)-1 , a2) ; 
  }
  rep(i , 1 , n){
    upd(f(a[i]+1) , f(b[i]+1)-1 , 2) ;
    for(auto [x, w] : v3[i]){
      x.F = f(x.F) ;
      x.S = f(x.S) ;  
      ans = (ans + w * que(x.F,x.S-1))%mod ;
    }
    upd(f(a[i]+1) , f(b[i]+1)-1 , a2) ;
  }
  bui() ;
  per(i , n ,1 ){
    for(auto [x, w] : v2[i]){
      x.F = f(x.F) ;
      x.S = f(x.S) ;  
      ans = (ans + w * que(x.F,x.S-1))%mod ;
    }
    upd(f(a[i]+1) ,f(b[i]+1)-1 , a2) ; 
  }
  cout <<ans*po(2,n)%mod << "\n" ;
}
/*

*/

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