제출 #1105643

#제출 시각아이디문제언어결과실행 시간메모리
1105643alexddFlooding Wall (BOI24_wall)C++17
12 / 100
184 ms62792 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1e9+7; int n,maxh,cate; int a[500005],b[500005]; int prefmax[500005],suffmax[500005]; int p2[1000005],inv2; int put(int x, int exp) { if(exp==0) return 1; if(exp%2==0) return put(x*x%MOD,exp/2); else return put(x*x%MOD,exp/2)*x%MOD; } map<int,int> mp,nrm; int inv[2000005]; int aint[8000005],lazy[8000005]; void build(int nod, int st, int dr) { lazy[nod]=1; if(st==dr) { aint[nod] = inv[dr]-inv[st-1]; return; } int mij=(st+dr)/2; build(nod*2,st,mij); build(nod*2+1,mij+1,dr); aint[nod] = (aint[nod*2] + aint[nod*2+1])%MOD; } void propagate(int nod) { if(lazy[nod]==1) return; lazy[nod*2] = (lazy[nod*2]*lazy[nod])%MOD; lazy[nod*2+1] = (lazy[nod*2+1]*lazy[nod])%MOD; aint[nod*2] = (aint[nod*2]*lazy[nod])%MOD; aint[nod*2+1] = (aint[nod*2+1]*lazy[nod])%MOD; lazy[nod]=1; } void upd(int nod, int st, int dr, int le, int ri, int newv) { assert(newv!=0); if(le>ri) return; if(le==st && dr==ri) { lazy[nod] = (lazy[nod]*newv)%MOD; aint[nod] = (aint[nod]*newv)%MOD; return; } propagate(nod); int mij=(st+dr)/2; upd(nod*2,st,mij,le,min(mij,ri),newv); upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv); aint[nod] = (aint[nod*2] + aint[nod*2+1])%MOD; } int qry(int nod, int st, int dr, int le, int ri) { if(le>ri) return 0; if(le==st && dr==ri) return aint[nod]; propagate(nod); int mij=(st+dr)/2; return (qry(nod*2,st,mij,le,min(mij,ri)) + qry(nod*2+1,mij+1,dr,max(mij+1,le),ri))%MOD; } int calc_0(int inc[4][500005]) { int rez=0; build(1,1,cate); for(int i=1;i<=n;i++) { rez = (rez + p2[n-i]*qry(1,1,cate,nrm[inc[0][i]],maxh))%MOD; upd(1,1,cate,nrm[b[i]+1],maxh,2); } return rez; } int calc_1(int inc[4][500005]) { int rez=0; build(1,1,cate); for(int i=n;i>0;i--) { rez = (rez + qry(1,1,cate,nrm[inc[1][i]],maxh)*p2[i-1])%MOD; upd(1,1,cate,nrm[b[i]+1],maxh,2); } return rez; } int calc_2(int inc[4][500005]) { int rez=0; build(1,1,cate); for(int i=1;i<=n;i++) upd(1,1,cate,nrm[b[i]+1],maxh,2); for(int i=1;i<=n;i++) { upd(1,1,cate,nrm[b[i]+1],maxh,inv2); rez = (rez + qry(1,1,cate,nrm[inc[2][i]],maxh))%MOD; upd(1,1,cate,nrm[b[i]+1],maxh,2); } return rez; } int calc_3(int inc[4][500005]) { int rez=0; for(int i=1;i<=n;i++) { rez = (rez + 5LL*MOD + inv[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; inv2 = put(2,MOD-2); 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]+1); mp[a[i]]++; mp[a[i]+1]++; //mp[b[i]]++; mp[b[i]+1]++; } //mp[maxh]++; //mp[0]++; mp[1]++; for(auto it:mp) { if(!it.second) continue; nrm[it.first] = ++cate; inv[cate] = it.first; } maxh = nrm[maxh]; 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...