이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define sz(s) (int)s.size()
#define in insert
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define int ll
const int MAX=1e6+10;
const int mod=1e9+7;
int n;
int a[MAX],b[MAX];
vector<int> vec;
struct segtree{
int t[4*MAX],t1[4*MAX],add[4*MAX];
void init(int n){
for(int i=1;i<=4*n;i++){
t[i]=t1[i]=0;
add[i]=1;
}
}
void upd(int v,int x){
t[v]=t[v]*x%mod;
t1[v]=t1[v]*x%mod;
add[v]=add[v]*x%mod;
}
void push(int v){
if(add[v]!=1){
upd(2*v,add[v]);
upd(2*v+1,add[v]);
add[v]=1;
}
}
void update(int v,int tl,int tr,int l,int r,int x){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
upd(v,x);
return;
}
push(v);
int tm=(tl+tr)/2;
update(2*v,tl,tm,l,r,x);
update(2*v+1,tm+1,tr,l,r,x);
t[v]=(t[2*v]+t[2*v+1])%mod;
t1[v]=(t1[2*v]+t1[2*v+1])%mod;
}
void set(int v,int tl,int tr,int pos,int x){
if(tl==tr){
t[v]=x;
t1[v]=vec[tl]*x%mod;
return;
}
push(v);
int tm=(tl+tr)/2;
if(pos<=tm)set(2*v,tl,tm,pos,x);
else set(2*v+1,tm+1,tr,pos,x);
t[v]=(t[2*v]+t[2*v+1])%mod;
t1[v]=(t1[2*v]+t1[2*v+1])%mod;
}
int get(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return 0;
if(l<=tl&&tr<=r)return t[v];
push(v);
int tm=(tl+tr)/2;
return (get(2*v,tl,tm,l,r)+get(2*v+1,tm+1,tr,l,r))%mod;
}
int getT(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return 0;
if(l<=tl&&tr<=r)return t1[v];
push(v);
int tm=(tl+tr)/2;
return (getT(2*v,tl,tm,l,r)+getT(2*v+1,tm+1,tr,l,r))%mod;
}
}T;
int pw[MAX];
void solve(){
cin>>n;
pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=(pw[i-1]*2)%mod;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
vec.pb(0);
for(int i=1;i<=n;i++)vec.pb(a[i]),vec.pb(b[i]);
sort(all(vec));
vec.erase(unique(all(vec)),vec.end());
for(int i=1;i<=n;i++){
a[i]=lb(all(vec),a[i])-vec.begin();
b[i]=lb(all(vec),b[i])-vec.begin();
if(a[i]>b[i])swap(a[i],b[i]);
}
int ans=0;
for(int i=1;i<=n;i++){
ans-=(a[i]+b[i])*pw[n-1]%mod;
if(ans<0)ans+=mod;
}
T.init(2*n+1);
T.set(1,0,2*n,0,1);
for(int i=1;i<=n;i++){
int x=T.get(1,0,2*n,0,a[i]);
int y=(T.get(1,0,2*n,0,b[i])+T.get(1,0,2*n,b[i],b[i]))%mod;
T.set(1,0,2*n,a[i],x);
T.set(1,0,2*n,b[i],y);
T.update(1,0,2*n,0,a[i]-1,0);
T.update(1,0,2*n,b[i]+1,2*n,2);
ans+=T.getT(1,0,2*n,0,2*n)*pw[n-i]%mod;
if(ans>=mod)ans-=mod;
}
ans-=T.getT(1,0,2*n,0,2*n)*n%mod;
if(ans<0)ans+=mod;
T.init(2*n+1);
T.set(1,0,2*n,0,1);
for(int i=n;i>=1;i--){
int x=T.get(1,0,2*n,0,a[i]);
int y=(T.get(1,0,2*n,0,b[i])+T.get(1,0,2*n,b[i],b[i]))%mod;
T.set(1,0,2*n,a[i],x);
T.set(1,0,2*n,b[i],y);
T.update(1,0,2*n,0,a[i]-1,0);
T.update(1,0,2*n,b[i]+1,2*n,2);
ans+=T.getT(1,0,2*n,0,2*n)*pw[i-1]%mod;
if(ans>=mod)ans-=mod;
}
cout<<ans<<"\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |