제출 #1105416

#제출 시각아이디문제언어결과실행 시간메모리
1105416alexddFlooding Wall (BOI24_wall)C++17
0 / 100
5095 ms55000 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 calc_0(int inc[4][500005]) { int rez=0; for(int i=1;i<=n;i++) { for(int h=inc[0][i];h<=maxh;h++) { int cle=0; for(int j=1;j<i;j++) if(b[j] < h) cle++; rez = (rez + p2[n-i+cle])%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 += maxh - inc[3][i] + 1; } 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] = min(prefmax[i-1], suffmax[i+1]) + 1; 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; } /*rez=0; for(int i=1;i<=n;i++) { for(int h=a[i]+1;h<=maxh;h++) { int cle=0,cri=0,ble=1,bri=1; for(int j=1;j<i;j++) { if(b[j] < h) cle++; if(a[j] >= h) ble = 0; } for(int j=i+1;j<=n;j++) { if(b[j] < h) cri++; if(a[j] >= h) bri = 0; } int aux = (p2[i-1] - p2[cle]*ble + MOD) * (p2[n-i] - p2[cri]*bri + MOD)%MOD; rez = (rez + aux)%MOD; if(h > b[i]) rez = (rez + aux)%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...