| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1326868 | boclobanchat | Flooding Wall (BOI24_wall) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
struct value { int x,idx,p; };
bool comp(value a,value b)
{
if(a.x==b.x)
{
if(a.idx==b.idx) return a.p<b.p;
return a.idx<b.idx;
}
return a.x<b.x;
}
const int MAXN=1e6+5;
const long long mod=1e9+7;
value val[MAXN];
pair<int,int> P[MAXN];
pair<long long,long long> A[MAXN],F[2][MAXN],G[2][MAXN];
struct node
{
long long sum,cnt,f,lazy;
};
node seg[MAXN*4];
node merge(node a,node b)
{
return {(a.sum+b.sum)%mod,(a.cnt+b.cnt)%mod,(a.f+b.f)%mod,1};
}
void build(int l,int r,int pos)
{
seg[pos]={0,0,0,0,1};
if(l==r) return ;
int mid=(l+r)/2;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
}
void down(int pos)
{
long long val=seg[pos].lazy;
if(val==1) return ;
seg[pos*2].sum=seg[pos*2].sum*val%mod,seg[pos*2].cnt=seg[pos*2].cnt*val%mod;
seg[pos*2].f=seg[pos*2].f*val%mod,seg[pos*2].lazy=seg[pos*2].lazy*val%mod;
seg[pos*2+1].sum=seg[pos*2+1].sum*val%mod,seg[pos*2+1].cnt=seg[pos*2+1].cnt*val%mod;
seg[pos*2+1].f=seg[pos*2+1].f*val%mod,seg[pos*2+1].lazy=seg[pos*2+1].lazy*val%mod;
seg[pos].lazy=1;
}
void updset(int l,int r,int i,long long sum,long long cnt,int he,int pos)
{
if(i<l||r<i) return ;
if(l==r)
{
seg[pos]={(sum-cnt*val[i].x%mod*he%mod+mod)%mod,cnt,cnt*val[i].x%mod,1};
return ;
}
int mid=(l+r)/2;
down(pos);
updset(l,mid,i,sum,cnt,he,pos*2);
updset(mid+1,r,i,sum,cnt,he,pos*2+1);
seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
void update(int l,int r,int u,int v,long long val,int pos)
{
if(v<l||r<u) return ;
if(u<=l&&r<=v)
{
seg[pos].sum=seg[pos].sum*val%mod,seg[pos].cnt=seg[pos].cnt*val%mod;
seg[pos].f=seg[pos].f*val%mod,seg[pos].lazy=seg[pos].lazy*val%mod;
return ;
}
int mid=(l+r)/2;
down(pos);
update(l,mid,u,v,val,pos*2);
update(mid+1,r,u,v,val,pos*2+1);
seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
node get(int l,int r,int u,int v,int pos)
{
if(u<=l&&r<=v) return seg[pos];
int mid=(l+r)/2;
down(pos);
if(v<=mid) return get(l,mid,u,v,pos*2);
if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
return merge(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>A[i].first;
for(int i=1;i<=n;i++)
{
cin>>A[i].second;
if(A[i].first>A[i].second) swap(A[i].first,A[i].second);
val[++cnt]={A[i].first,i,0},val[++cnt]={A[i].second,i,1};
}
sort(val+1,val+cnt+1,comp);
for(int i=1;i<=cnt;i++) if(val[i].p) P[val[i].idx].second=i;
else P[val[i].idx].first=i;
build(0,cnt,1);
updset(0,cnt,0,0,1,0,1);
for(int i=1;i<=n;i++)
{
int x=P[i].first,y=P[i].second;
node f1=get(0,cnt,0,x-1,1),f2=get(0,cnt,0,y-1,1);
update(0,cnt,0,x-1,0,1);
update(0,cnt,y+1,cnt,2,1);
F[0][i]={(f1.sum+f1.f*(i-1))%mod,f1.cnt};
F[1][i]={(f2.sum+f2.f*(i-1))%mod,f2.cnt};
updset(0,cnt,x,F[0][i].first,F[0][i].second,i-1,1);
updset(0,cnt,y,F[1][i].first,F[1][i].second,i-1,1);
}
build(0,cnt,1);
updset(0,cnt,0,0,1,0,1);
for(int i=n;i;i--)
{
int x=P[i].first,y=P[i].second;
node f1=get(0,cnt,0,x-1,1),f2=get(0,cnt,0,y-1,1);
update(0,cnt,0,x-1,0,1);
update(0,cnt,y+1,cnt,2,1);
G[0][i]={(f1.sum+f1.f*(n-i))%mod,f1.cnt};
G[1][i]={(f2.sum+f2.f*(n-i))%mod,f2.cnt};
updset(0,cnt,x,G[0][i].first,G[0][i].second,n-i,1);
updset(0,cnt,y,G[1][i].first,G[1][i].second,n-i,1);
}
long long ans=0,pw=1;
for(int i=1;i<n;i++) pw=pw*2%mod;
for(int i=1;i<=n;i++)
{
ans=(ans+F[0][i].first*G[0][i].second%mod+F[0][i].second*G[0][i].first%mod+F[0][i].second*G[0][i].second%mod*A[i].first%mod)%mod;
ans=(ans+F[1][i].first*G[1][i].second%mod+F[1][i].second*G[1][i].first%mod+F[1][i].second*G[1][i].second%mod*A[i].second%mod)%mod;
ans=(ans-(A[i].first+A[i].second)%mod*pw%mod+mod)%mod;
}
cout<<ans;
}