QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#416983 | #8712. Flooding Wall | _set_# | 0 | 142ms | 131508kb | C++17 | 6.0kb | 2024-05-22 12:04:26 | 2024-05-22 12:04:27 |
Judging History
answer
// what is matter? never mind.
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int __int128
//#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 1000000007
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,modint b){return a.x==b.x;}
friend bool operator !=(modint a,modint b){return a.x!=b.x;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 1000005
#define inf 0x3f3f3f3f
int n,a[maxn],b[maxn],t[maxn],m;
modint res,del;
struct bit{
vector<int>tr;
int n;
void init(int N){n=N,tr=vector<int>(N+1,0);}
void add(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
int ask(int x){
// cout<<"ask "<<x<<"\n";
x=min(x,n);
// x=max(x,0);
int s=0;
for(;x;x^=x&-x)s+=tr[x];
return s;
}
void down(){For(i,1,n)tr[i]+=tr[i^(i&-i)];}
}trb,tra;
modint mula[maxn],mulb[maxn];
struct node{
modint cnt,sum;
};
node operator +(node a,node b){
return {a.cnt+b.cnt,a.sum+b.sum};
}
node Add(node a,modint w){
a.sum+=a.cnt*w;
return a;
}
struct NODE{
int len;
modint cnt,sum,ds;
// sum_ d[i]*cnt[i]
}tr[maxn<<2];
modint mul[maxn<<2],add[maxn<<2];
void up(int p){
auto &l=tr[p<<1],&r=tr[p<<1|1];
tr[p].cnt=l.cnt+r.cnt;
tr[p].sum=l.sum+r.sum;
tr[p].ds=l.ds+r.ds;
}
void pt(int p,modint mu,modint ad){
if(mu.x==1 && ad.x==0) return;
if(mu.x!=1) tr[p].cnt*=mu,tr[p].sum*=mu;tr[p].ds*=mu;
if(ad.x!=1) tr[p].sum+=ad*tr[p].ds;
add[p]=add[p]+ad;
if(mu.x!=1) mul[p]*=mu;
}
void down(int p){
if(1){
pt(p<<1,mul[p],add[p]);
pt(p<<1|1,mul[p],add[p]);
mul[p]=1,add[p]=0;
}
}
void build(int p,int l,int r){
tr[p]={0,0,0,0};
mul[p]=1,add[p]=0;
tr[p].len=r-l+1;
if(l==r){
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
up(p);
}
void upd(int p,int l,int r,int x,node y){
if(l==r){
tr[p].cnt+=y.cnt;
tr[p].sum+=y.sum;
tr[p].ds+=y.cnt*t[l];
return;
}
int mid=l+r>>1;down(p);
if(x<=mid)upd(p<<1,l,mid,x,y);
else upd(p<<1|1,mid+1,r,x,y); up(p);
}
void mdf(int p,int l,int r,int ql,int qr,modint M,modint A){
if(ql>qr)return;
if(l>=ql&&r<=qr)return pt(p,M,A);
int mid=l+r>>1; down(p);
if(ql<=mid) mdf(p<<1,l,mid,ql,qr,M,A);
if(qr>mid) mdf(p<<1|1,mid+1,r,ql,qr,M,A);
up(p);
}
node ask(int p,int l,int r,int ql,int qr){
if(ql>qr)return {0,0};
if(l>=ql&&r<=qr)return {tr[p].cnt,tr[p].sum};
int mid=l+r>>1; down(p);
node res={0,0};
if(ql<=mid)res=ask(p<<1,l,mid,ql,qr);
if(qr>mid)res=res+ask(p<<1|1,mid+1,r,ql,qr);
return res;
}
node f[maxn],g[maxn];
void solve(int bo)
{
// bo=0 : {max} max max
// bo=1 : max max {max}
trb.init(m);
tra.init(m);
Rep(i,n,1){
mula[i]=mulb[i]=0;
if(!tra.ask(m-(a[i]+(!bo))+1)) mula[i]=qpow(2,trb.ask(a[i]-bo));
if(!tra.ask(m-(b[i]+(!bo))+1)) mulb[i]=qpow(2,trb.ask(b[i]-bo));
trb.add(b[i],1);
tra.add(m-a[i]+1,1);
}
build(1,1,m);
auto mul=[&](int l,int r,int x){
mdf(1,1,m,l,r,x,0);
};
// len,\sum cnt[i],\sum sum[i],\sum d[i],\sum d[i]*cnt[i]
auto add=[&](int l,node tmp){
upd(1,1,m,l,tmp);
};
auto pushall=[&](){
mdf(1,1,m,1,m,1,1);
};
For(i,1,n){
// cout<<"i: "<<i<<"\n";
node suma=ask(1,1,m,1,a[i]-(!bo));
node sumb=ask(1,1,m,1,b[i]-(!bo));
if(i==1) suma.cnt+=1,sumb.cnt+=1;
node tmp=suma;
if(bo) tmp=Add(tmp,t[a[i]]);
res+=tmp.sum*mula[i];
tmp=sumb;
if(bo) tmp=Add(tmp,t[b[i]]);
res+=tmp.sum*mulb[i];
mul(1,a[i]-(!bo),0);
mul(b[i]-(!bo)+1,m,2);
add(b[i],sumb);
add(a[i],suma);
pushall();
}
// cout<<"res "<<res.x<<"\n";
}
signed main()
{
n=read();
For(i,1,n)a[i]=read();
For(i,1,n)b[i]=read();
For(i,1,n){
t[++m]=a[i],t[++m]=b[i];
if(a[i]>b[i])swap(a[i],b[i]);
}
del=0;
For(i,1,n)del+=a[i],del+=b[i];
del*=qpow(2,n-1);
sort(t+1,t+m+1),m=unique(t+1,t+m+1)-t-1;
For(i,1,n)a[i]=lower_bound(t+1,t+m+1,a[i])-t,b[i]=lower_bound(t+1,t+m+1,b[i])-t;
solve(0);
reverse(a+1,a+n+1);
reverse(b+1,b+n+1);
solve(1);
// cout<<"res "<<res.x<<"\n";
res-=del;
cout<<res.x;
return 0;
}
/*
1
1 2 2 1
1 2 2 1
1 2 2 1
1 2 2 1
5 4
*/
/*
*/
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 126040kb
input:
4 1 1 1 1 2 2 2 2
output:
999999942
result:
wrong answer 1st lines differ - expected: '6', found: '999999942'
Subtask #2:
score: 0
Wrong Answer
Test #23:
score: 0
Wrong Answer
time: 3ms
memory: 126664kb
input:
100 948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...
output:
267050520
result:
wrong answer 1st lines differ - expected: '164439470', found: '267050520'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Wrong Answer
Test #57:
score: 0
Wrong Answer
time: 142ms
memory: 131508kb
input:
500000 1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...
output:
523842497
result:
wrong answer 1st lines differ - expected: '869044223', found: '523842497'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%