제출 #1096281

#제출 시각아이디문제언어결과실행 시간메모리
1096281epicci23Flooding Wall (BOI24_wall)C++17
12 / 100
2274 ms100276 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){ return (a+b)%MOD; } inline int eks(int a,int b){ return (a-b+MOD)%MOD; } inline int mult(int a,int b){ return (a*b)%MOD; } 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(l==r && !acik[l]) return; int u=lazy[rt]; lazy[rt]=1; sum[rt]=mult(sum[rt],u); if(l==r) return; 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 << "actim: " << l << ' ' << u << ' ' << lazy[rt] << '\n'; acik[l]=1; sum[rt]=u; push(rt,l,r); //cout << "l: " << l << ' ' << sum[rt] << '\n'; 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]); } }; 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=1;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...