QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416974#8712. Flooding Wall_set_#0 204ms67948kbC++176.5kb2024-05-22 11:50:592024-05-22 11:51:00

Judging History

This is the latest submission verdict.

  • [2024-05-22 11:51:00]
  • Judged
  • Verdict: 0
  • Time: 204ms
  • Memory: 67948kb
  • [2024-05-22 11:50:59]
  • Submitted

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 500005
#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){
	tr[p].cnt*=mu,tr[p].sum*=mu,tr[p].ds*=mu;
	tr[p].sum+=ad*tr[p].ds;
	add[p]=add[p]*mu+ad;
	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};
	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";
	
//	memset(f,0,sizeof f);
//	f[0]={1,0};
//	For(i,1,n){
////		cout<<"i: "<<i<<"\n";
//		auto trs=[&](int x,modint w){
//			node sum;
//			For(i,0,m){
//				g[max(i,x)]=g[max(i,x)]+f[i];
//				if(i<=x-(!bo)) sum=sum+f[i];
//			}
////			cout<<"trs "<<x<<" "<<w.x<<"\n";
//			if(bo) sum=add(sum,t[x]);
////			cout<<"sum "<<sum.cnt.x<<" "<<sum.sum.x<<"\n";
//			res+=sum.sum*w;
//		};
//		trs(a[i],mula[i]),trs(b[i],mulb[i]);
//		For(j,0,m) f[j]=g[j],g[j]={0,0};
//		For(j,1,m) f[j]=add(f[j],t[j]);
////		For(j,1,m) cout<<f[j].cnt.x<<" "<<f[j].sum.x<<"\n"; cout<<"-----\n";
//	}
//	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

*/

/*
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 3ms
memory: 67568kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 67444kb

input:

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

output:

822720

result:

wrong answer 1st lines differ - expected: '21116', found: '822720'

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 0ms
memory: 66432kb

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:

515573110

result:

wrong answer 1st lines differ - expected: '164439470', found: '515573110'

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: 204ms
memory: 67948kb

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:

835685115

result:

wrong answer 1st lines differ - expected: '869044223', found: '835685115'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%