이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn=5e5+69;
const ll mod=1e9+7;
const ll inf=1e18;
int n,a[maxn],b[maxn];
int mu2[maxn],chia2;
namespace subdevaicalon
{
int m;
vector<int> tmp;
int aa[maxn],bb[maxn],res[maxn];
struct segtree
{
int f[maxn*8],g[maxn*8],lazy[maxn*8];
void push(int id)
{
int t=lazy[id];
f[id*2]=(f[id*2]*t)%mod;
f[id*2+1]=(f[id*2+1]*t)%mod;
g[id*2]=(g[id*2]*t)%mod;
g[id*2+1]=(g[id*2+1]*t)%mod;
lazy[id*2]=lazy[id*2]*t%mod;
lazy[id*2+1]=lazy[id*2+1]*t%mod;
lazy[id]=-1;
}
void Add(int u,int val,int id=1,int l=0,int r=m)
{
if (l==r)
{
f[id]+=val;
g[id]=f[id]*tmp[l];
f[id]%=mod;
g[id]%=mod;
return;
}
if (lazy[id]!=-1) push(id);
int mid=l+r>>1;
if (u<=mid) Add(u,val,id*2,l,mid);
else Add(u,val,id*2+1,mid+1,r);
f[id]=(f[id*2]+f[id*2+1])%mod;
g[id]=(g[id*2]+g[id*2+1])%mod;
}
void Mul(int u,int v,int val,int id=1,int l=0,int r=m)
{
if (u>r || v<l) return;
if (u<=l&& r<=v)
{
f[id]=(f[id]*val)%mod;
g[id]=(g[id]*val)%mod;
lazy[id]=lazy[id]*val%mod;
// if (u==0 && v==m) cerr<< id<<'\n';
return;
}
int mid=l+r>>1;
if (lazy[id]!=-1) push(id);
Mul(u,v,val,id*2,l,mid);
Mul(u,v,val,id*2+1,mid+1,r);
f[id]=(f[id*2]+f[id*2+1])%mod;
g[id]=(g[id*2]+g[id*2+1])%mod;
}
int Get_fsum(int u,int v,int id=1,int l=0,int r=m)
{
if (u>r || v<l) return 0;
if (u<=l && r<=v) return f[id];
int mid=l+r>>1;
if (lazy[id]!=-1) push(id);
return (Get_fsum(u,v,id*2,l,mid) + Get_fsum(u,v,id*2+1,mid+1,r))%mod;
}
int Get_gsum(int u,int v,int id=1,int l=0,int r=m)
{
if (u>r || v<l) return 0;
if (u<=l && r<=v) return g[id];
int mid=l+r>>1;
if (lazy[id]!=-1) push(id);
return (Get_gsum(u,v,id*2,l,mid) + Get_gsum(u,v,id*2+1,mid+1,r))%mod;
}
}tree;
void Update(int i)
{
tree.Mul(bb[i]+1,m,2);
tree.Add(bb[i],tree.Get_fsum(0,bb[i]));
tree.Add(aa[i],tree.Get_fsum(0,aa[i]-1));
tree.Mul(0,aa[i]-1,0);
}
int Get(int i)
{
int res=0;
int r1=tree.Get_fsum(bb[i]+1,m), r2=tree.Get_gsum(bb[i]+1,m);
r1=r1*chia2%mod;
r2=r2*chia2%mod;
res=r2+mod-(r1*b[i]%mod);
res%=mod;
int fb=tree.Get_fsum(bb[i],bb[i]);
int xx=tree.Get_fsum(aa[i],bb[i]-1);
fb-=xx;
fb=fb*chia2%mod;
r1+=xx+fb;
r2+=tree.Get_gsum(aa[i],bb[i]-1);
r2+=fb*b[i];
r1%=mod;
r2%=mod;
res+=r2+mod-(r1*a[i]%mod);
return res%mod;
}
void sol()
{
for1(i,1,n)
{
tmp.pb(a[i]);
tmp.pb(b[i]);
}
tmp.pb(0);
sort(all(tmp));
tmp.resize(unique(all(tmp))-tmp.begin());
m=tmp.size();
for1(i,1,n)
{
aa[i]=lower_bound(all(tmp),a[i])-tmp.begin();//tmp[aa[i]]=a[i]
bb[i]=lower_bound(all(tmp),b[i])-tmp.begin();
}
for1(i,0,m*4) tree.lazy[i]=-1;
tree.Add(0,1);
for1(i,1,n)
{
Update(i);
// if (i==1)cerr << tree.Get_fsum(1,1)<<'\n';
res[i]=Get(i)*mu2[n-i]%mod;
}
for1(i,0,m*4)
{
tree.lazy[i]=-1;
// tree.f[i]=0;
// tree.g[i]=0;
}
tree.Mul(0,m,0);
tree.Add(0,1);
for2(i,n,1)
{
Update(i);
// cerr<< Get(i)<<'\n';
res[i]=(res[i]+ (Get(i)*mu2[i-1]%mod))%mod;
}
int ans=0;
for1(i,1,n)
{
ans=ans+res[i]+mod-Get(i);
ans%=mod;
}
cout << ans;
}
}
void sol()
{
// cerr<< pw(2,mod-2);
chia2=500000004;
cin >> n;
for1(i,1,n)
{
cin >> a[i];
// cerr<< "aaa\n";
}
bool is_sub2=1;
mu2[0]=1;
for1(i,1,n) mu2[i]=mu2[i-1]*2%mod;
for1(i,1,n)
{
cin >> b[i];
if (b[i]<a[i]) swap(a[i],b[i]);
if (a[i]!=1 || b[i]!=2) is_sub2=0;
}
subdevaicalon::sol();
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("wall.inp","r",stdin);
freopen("wall.out","w",stdout);
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In member function 'void subdevaicalon::segtree::Add(ll, ll, ll, ll, ll)':
Main.cpp:51:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid=l+r>>1;
| ~^~
Main.cpp: In member function 'void subdevaicalon::segtree::Mul(ll, ll, ll, ll, ll, ll)':
Main.cpp:68:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid=l+r>>1;
| ~^~
Main.cpp: In member function 'll subdevaicalon::segtree::Get_fsum(ll, ll, ll, ll, ll)':
Main.cpp:79:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int mid=l+r>>1;
| ~^~
Main.cpp: In member function 'll subdevaicalon::segtree::Get_gsum(ll, ll, ll, ll, ll)':
Main.cpp:87:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid=l+r>>1;
| ~^~
Main.cpp: In function 'void sol()':
Main.cpp:176:10: warning: variable 'is_sub2' set but not used [-Wunused-but-set-variable]
176 | bool is_sub2=1;
| ^~~~~~~
Main.cpp: In function 'int32_t main()':
Main.cpp:194:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | freopen("wall.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:195:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
195 | freopen("wall.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |