제출 #1105439

#제출 시각아이디문제언어결과실행 시간메모리
1105439alexddFlooding Wall (BOI24_wall)C++17
36 / 100
5061 ms60488 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]; int put(int a, int exp) { if(exp==0) return 1; if(exp%2==0) return put(a*a%MOD,exp/2); else return put(a*a%MOD,exp/2)*a%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]],nrm[maxh]))%MOD; upd(1,1,cate,nrm[b[i]+1],nrm[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]],nrm[maxh])*p2[i-1])%MOD; upd(1,1,cate,nrm[b[i]+1],nrm[maxh],2); } 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]); mp[a[i]]++; mp[a[i]+1]++; mp[b[i]]++; mp[b[i]+1]++; } mp[0]++; mp[1]++; //for(int i=0;i<=maxh;i++) // mp[i]++; for(auto it:mp) { if(!it.second) continue; nrm[it.first] = ++cate; inv[cate] = it.first; } 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...