QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416983#8712. Flooding Wall_set_#0 142ms131508kbC++176.0kb2024-05-22 12:04:262024-05-22 12:04:27

Judging History

This is the latest submission verdict.

  • [2024-05-22 12:04:27]
  • Judged
  • Verdict: 0
  • Time: 142ms
  • Memory: 131508kb
  • [2024-05-22 12:04:26]
  • 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 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%