Submission #999450

#TimeUsernameProblemLanguageResultExecution timeMemory
999450AlperenT_Flooding Wall (BOI24_wall)C++17
12 / 100
354 ms172960 KiB
#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" ; } /* */
#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...