Submission #1151192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151192		dpsaveslives	Flooding Wall (BOI24_wall)	C++20	100 / 100	1970 ms	67168 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=5e5+10,mod=1e9+7,inv2=(mod+1)/2;
inline int add(int x,int y){ return x+y>=mod?x+y-mod:x+y; }
inline int dec(int x,int y){ return x>=y?x-y:x+mod-y; }
struct node{
	int v,p;
	inline friend bool operator<(const node &a,const node &b){
		return a.v==b.v?a.p<b.p:a.v<b.v;
	}
}a[N<<1];
struct TD{
	int a,b,c;
	TD(int A=0,int B=0,int C=0){ a=A,b=B,c=C; }
	inline friend TD operator +(const TD &a,const TD &b){
		return TD(add(a.a,b.a),add(a.b,b.b),add(a.c,b.c));
	}
	inline friend TD operator *(const TD &a,const int &b){
		return TD(1ll*a.a*b%mod,1ll*a.b*b%mod,1ll*a.c*b%mod);
	}
};
int n,pw[N],ipw[N],fa[N],c[N],f[N][2],p[N][2],g[N][2],q[N][2];
inline int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
struct BIT{
	#define lowbit(x) (x&-x)
	int t[N];
	inline void clear(){
		for(int i=1;i<=n;i++)
			t[i]=0;
	}
	inline void add(int x,int v){
		for(int i=x;i<=n;i+=lowbit(i))
			t[i]+=v;
	}
	inline int query(int x){
		int s=0;
		for(int i=x;i;i-=lowbit(i))
			s+=t[i];
		return s;
	}
}T0;
struct Segment_Tree{
	#define ls (rt<<1)
	#define rs (rt<<1|1)
	TD vs[N<<2];
	int tag[N<<2];
	inline void pushadd(int rt,TD v){
		vs[rt]=vs[rt]+v*tag[rt];
	}
	inline void pushtag(int rt,int v){
		tag[rt]=1ll*tag[rt]*v%mod;
	}
	inline void pushdown(int rt){
		if(vs[rt].a||vs[rt].b||vs[rt].c){
			pushadd(ls,vs[rt]);
			pushadd(rs,vs[rt]);
			vs[rt]=TD();
		}
		if(tag[rt]!=1){
			pushtag(ls,tag[rt]);
			pushtag(rs,tag[rt]);
			tag[rt]=1;
		}
	}
	inline void build(int rt,int l,int r){
		tag[rt]=1,vs[rt]=TD();
		if(l==r){ return ; }
		int mid=l+r>>1;
		build(ls,l,mid),build(rs,mid+1,r);
	}
	inline void add(int rt,int l,int r,int L,int R,TD v){
		if(L>R) return ;
		if(L<=l&&r<=R) return pushadd(rt,v);
		pushdown(rt);
		int mid=l+r>>1;
		if(L<=mid) add(ls,l,mid,L,R,v);
		if(R>mid) add(rs,mid+1,r,L,R,v);
	}
	inline void mul(int rt,int l,int r,int L,int R,int v){
		if(L>R) return ;
		if(L<=l&&r<=R) return pushtag(rt,v);
		pushdown(rt);
		int mid=l+r>>1;
		if(L<=mid) mul(ls,l,mid,L,R,v);
		if(R>mid) mul(rs,mid+1,r,L,R,v);
	}
	inline TD query(int rt,int l,int r,int p){
		if(l==r) return vs[rt];
		pushdown(rt);
		int mid=l+r>>1;
		if(p<=mid) return query(ls,l,mid,p);
		else return query(rs,mid+1,r,p);
	}
}T;
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++){
        cin >> a[i].v;
        a[i].p = i;
	}
	for(int i=1;i<=n;i++){
        cin >> a[i+n].v;
        a[i+n].p = i;
	}
	pw[0]=ipw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=add(pw[i-1],pw[i-1]),
		ipw[i]=1ll*inv2*ipw[i-1]%mod;
	sort(a+1,a+n*2+1);
	for(int i=0;i<=n+1;i++)
		fa[i]=i;
	T.build(1,1,n);
	T.add(1,1,n,1,1,TD(0,0,1));
	for(int i=1;i<=n*2;i++){
		int v=a[i].v,t=a[i].p;
		TD res=T.query(1,1,n,t);
		f[t][c[t]]=(res.a+1ll*t*res.b)%mod;
		p[t][c[t]]=res.c;
		int ct=T0.query(t);
		int pt=find(t+1);
		if(pt==n+1) pt=n;
		T.add(1,1,n,t+1,pt,TD(dec(f[t][c[t]],1ll*t*v%mod*p[t][c[t]]%mod),1ll*v*p[t][c[t]]%mod,p[t][c[t]])*ipw[ct]);
		c[t]++;
		if(c[t]==1) fa[t]=t+1;
		if(c[t]==2) T0.add(t,1),T.mul(1,1,n,t,n,2);
	}
	for(int i=0;i<=n+1;i++)
		fa[i]=i,c[i]=0;
	T0.clear(),T.build(1,1,n);
	T.add(1,1,n,n,n,TD(0,0,1));
	int ans=0;
	for(int i=1;i<=n*2;i++){
		int v=a[i].v,t=a[i].p;
		TD res=T.query(1,1,n,t);
		g[t][c[t]]=(res.a+1ll*t*res.b)%mod;
		q[t][c[t]]=res.c;
		ans=(ans+1ll*v*p[t][c[t]]%mod*q[t][c[t]])%mod;
		int ct=T0.query(t);
		int pt=find(t-1);
		if(pt==0) pt=1;
		T.add(1,1,n,pt,t-1,TD(add(g[t][c[t]],1ll*t*v%mod*q[t][c[t]]%mod),mod-1ll*v*q[t][c[t]]%mod,q[t][c[t]])*pw[ct]);
		c[t]++;
		if(c[t]==1) fa[t]=t-1;
		if(c[t]==2) T0.add(t,1),T.mul(1,1,n,t,n,inv2);
	}
	for(int i=1;i<=n*2;i++)
		ans=dec(ans,1ll*pw[n-1]*a[i].v%mod);
	for(int i=1;i<=n;i++)
		ans=(ans+1ll*f[i][0]*q[i][0]+1ll*p[i][0]*g[i][0]+1ll*f[i][1]*q[i][1]+1ll*p[i][1]*g[i][1])%mod;
	cout << ans << "\n";
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30