oj.uz

Submission #999450

# Submission time Handle Problem Language Result Execution time Memory
999450 2024-06-15T13:58:07 Z AlperenT_ Flooding Wall (BOI24_wall) C++17
12 / 100
 354 ms 172960 KB 
#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])-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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47708 KB Output is correct
2 Correct 7 ms 47708 KB Output is correct
3 Correct 7 ms 47824 KB Output is correct
4 Correct 9 ms 47708 KB Output is correct
5 Correct 7 ms 47704 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 7 ms 47580 KB Output is correct
9 Correct 8 ms 47708 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Incorrect 7 ms 47708 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47820 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 7 ms 47708 KB Output is correct
6 Correct 9 ms 47764 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47704 KB Output is correct
9 Correct 7 ms 47708 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47708 KB Output is correct
13 Incorrect 8 ms 47708 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47820 KB Output is correct
2 Correct 8 ms 47708 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 7 ms 47708 KB Output is correct
6 Correct 9 ms 47764 KB Output is correct
7 Correct 8 ms 47708 KB Output is correct
8 Correct 7 ms 47704 KB Output is correct
9 Correct 7 ms 47708 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Correct 7 ms 47708 KB Output is correct
12 Correct 7 ms 47708 KB Output is correct
13 Incorrect 8 ms 47708 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47708 KB Output is correct
2 Correct 7 ms 47708 KB Output is correct
3 Correct 7 ms 47824 KB Output is correct
4 Correct 9 ms 47708 KB Output is correct
5 Correct 7 ms 47704 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 7 ms 47580 KB Output is correct
9 Correct 8 ms 47708 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Incorrect 7 ms 47708 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47704 KB Output is correct
2 Correct 9 ms 47816 KB Output is correct
3 Correct 7 ms 47708 KB Output is correct
4 Correct 7 ms 47576 KB Output is correct
5 Correct 7 ms 47960 KB Output is correct
6 Correct 7 ms 47708 KB Output is correct
7 Correct 7 ms 47804 KB Output is correct
8 Correct 8 ms 47708 KB Output is correct
9 Correct 8 ms 47708 KB Output is correct
10 Correct 13 ms 52188 KB Output is correct
11 Correct 13 ms 52104 KB Output is correct
12 Correct 13 ms 52188 KB Output is correct
13 Correct 13 ms 52188 KB Output is correct
14 Correct 354 ms 172960 KB Output is correct
15 Correct 284 ms 172708 KB Output is correct
16 Correct 327 ms 172204 KB Output is correct
17 Correct 310 ms 172460 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47708 KB Output is correct
2 Correct 7 ms 47708 KB Output is correct
3 Correct 7 ms 47824 KB Output is correct
4 Correct 9 ms 47708 KB Output is correct
5 Correct 7 ms 47704 KB Output is correct
6 Correct 8 ms 47708 KB Output is correct
7 Correct 7 ms 47708 KB Output is correct
8 Correct 7 ms 47580 KB Output is correct
9 Correct 8 ms 47708 KB Output is correct
10 Correct 7 ms 47708 KB Output is correct
11 Incorrect 7 ms 47708 KB Output isn't correct
12 Halted 0 ms 0 KB -