제출 #1105426

#제출 시각아이디문제언어결과실행 시간메모리
1105426alexddFlooding Wall (BOI24_wall)C++17
36 / 100
5095 ms56920 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1e9+7; int n,maxh; int a[500005],b[500005]; int prefmax[500005],suffmax[500005]; int p2[1000005]; int cv[500005]; int calc_0(int inc[4][500005]) { int rez=0; for(int i=1;i<=maxh;i++) cv[i]=1; for(int i=1;i<=n;i++) { int aux=0; for(int h=inc[0][i];h<=maxh;h++) { /*int cle=0; for(int j=1;j<i;j++) if(b[j] < h) cle++; aux = (aux + p2[cle])%MOD;*/ aux = (aux + cv[h])%MOD; } rez = (rez + p2[n-i]*aux)%MOD; for(int j=b[i]+1;j<=maxh;j++) cv[j] = cv[j]*2%MOD; } return rez; } int calc_1(int inc[4][500005]) { int rez=0; for(int i=1;i<=n;i++) { for(int h=inc[1][i];h<=maxh;h++) { int cri=0; for(int j=i+1;j<=n;j++) if(b[j] < h) cri++; rez = (rez + p2[i-1+cri])%MOD; } } return rez; } int calc_2(int inc[4][500005]) { int rez=0; for(int i=1;i<=n;i++) { for(int h=inc[2][i];h<=maxh;h++) { int cnt=0; for(int j=1;j<=n;j++) if(j!=i && b[j] < h) cnt++; rez = (rez + p2[cnt])%MOD; } } return rez; } int calc_3(int inc[4][500005]) { int rez=0; for(int i=1;i<=n;i++) { rez = (rez + 5LL*MOD + maxh - inc[3][i] + 1)%MOD; } for(int i=1;i<n;i++) rez = rez*2%MOD; return rez; } int inc[2][4][500005]; signed main() { ios_base::sync_with_stdio(0);cin.tie(0); p2[0]=1; for(int i=1;i<=1000000;i++) p2[i] = p2[i-1]*2%MOD; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { cin>>b[i]; if(a[i]>b[i]) swap(a[i],b[i]); maxh = max(maxh, b[i]); } int rez=0; for(int i=1;i<=n;i++) prefmax[i] = max(prefmax[i-1], a[i]); for(int i=n;i>0;i--) suffmax[i] = max(suffmax[i+1], a[i]); for(int i=1;i<=n;i++) { inc[0][0][i] = inc[1][0][i] = prefmax[i-1]+1; inc[0][1][i] = inc[1][1][i] = suffmax[i+1]+1; inc[0][2][i] = inc[1][2][i] = max(prefmax[i-1], suffmax[i+1]) + 1; inc[0][3][i] = inc[1][3][i] = 0; for(int j=0;j<4;j++) { inc[0][j][i] = max(inc[0][j][i], a[i]+1); inc[1][j][i] = max(inc[1][j][i], b[i]+1); } } for(int i=0;i<2;i++) { rez = (rez + calc_3(inc[i]) + calc_2(inc[i]))%MOD; rez = (rez + MOD - calc_0(inc[i]))%MOD; rez = (rez + MOD - calc_1(inc[i]))%MOD; } cout<<rez; 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...