Submission #1191368

#TimeUsernameProblemLanguageResultExecution timeMemory
11913688pete8Flooding Wall (BOI24_wall)C++20
70 / 100
5096 ms198388 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;

const int mod=1e9+7,mxn=1e6,inf=1e9,minf=-1e9,lg=30,Mxn=1e9;

int n,k,m,d,q;
int val[mxn+10][2];
int P[mxn+10],sub[mxn+10][2],sz;

vector<int>comp;
struct seg{
	int dp[4*mxn+10],waysx[4*mxn+10],ways[4*mxn+10];
	pii lazy[4*mxn+10];
	//waysx= ways*x
	void init(){for(int i=0;i<=4*sz;i++)dp[i]=waysx[i]=ways[i]=0,lazy[i]={1,0};}
	
	void apply(int pos,pii x){
		dp[pos]=((x.f*dp[pos])%mod+(x.s*waysx[pos])%mod)%mod;
		waysx[pos]=(x.f*waysx[pos])%mod;
		ways[pos]=(x.f*ways[pos])%mod;
		lazy[pos]={(lazy[pos].f*x.f)%mod,((lazy[pos].s*x.f)%mod+(lazy[pos].f*x.s)%mod)%mod};
	}
	void push(int pos,int l,int r){
		if(lazy[pos].f==1&&lazy[pos].s==0)return;
		if(l!=r){
			apply(pos<<1,lazy[pos]);
			apply(pos<<1|1,lazy[pos]);
		}
		lazy[pos]={1,0};
	}
	void pull(int pos){
		dp[pos]=(dp[pos<<1]+dp[pos<<1|1])%mod;
		waysx[pos]=(waysx[pos<<1]+waysx[pos<<1|1])%mod;
		ways[pos]=(ways[pos<<1]+ways[pos<<1|1])%mod;
	}
	void update(int ql,int qr,int k,int pos=1,int l=0,int r=sz){
		if(l>qr||r<ql)return;
		if(ql<=l&&r<=qr)return void(apply(pos,{k,k}));
		push(pos,l,r);
		update(ql,qr,k,pos<<1,l,((l+r)>>1));
		update(ql,qr,k,pos<<1|1,((l+r)>>1)+1,r);
		pull(pos);
	}
	void modify(int qpos,int d,int w,int pos=1,int l=0,int r=sz){
		if(l>qpos||r<qpos)return;
		if(l==r){
			dp[pos]=(dp[pos]+d)%mod;
			ways[pos]=(ways[pos]+w)%mod;
			waysx[pos]=(waysx[pos]+(w*comp[l])%mod)%mod;
			return;
		}
		push(pos,l,r);
		if(qpos<=(l+r)>>1)modify(qpos,d,w,pos<<1,l,((l+r)>>1));
		else modify(qpos,d,w,pos<<1|1,((l+r)>>1)+1,r);
		pull(pos);
	}
	int getways(int ql,int qr,int pos=1,int l=0,int r=sz){
		if(l>qr||r<ql)return 0;
		if(ql<=l&&r<=qr)return ways[pos];
		push(pos,l,r);
		return (getways(ql,qr,pos<<1,l,((l+r)>>1))+getways(ql,qr,pos<<1|1,((l+r)>>1)+1,r))%mod;
	}
	int getdp(int ql,int qr,int pos=1,int l=0,int r=sz){
		if(l>qr||r<ql)return 0;
		if(ql<=l&&r<=qr)return dp[pos];
		push(pos,l,r);
		return (getdp(ql,qr,pos<<1,l,((l+r)>>1))+getdp(ql,qr,pos<<1|1,((l+r)>>1)+1,r))%mod;
	}
}t;


int pref[mxn+10],suf[mxn+10];
struct fen{
	int fwk[mxn+10];
	void init(){for(int i=0;i<=sz+1;i++)fwk[i]=0;}
	void update(int pos,int val){
		pos++;
		if(pos<=0)return;
		for(int i=pos;i<=sz+1;i+=(i&-i))fwk[i]+=val;
	}
	int qry(int pos){
		pos++;
		int sum=0;
		if(pos<=0)return 0;
		for(int i=pos;i>0;i-=(i&-i))sum+=fwk[i];
		return sum;
	}
}tmx;

int32_t main(){
	fastio
	cin>>n;
	int ans=0,ans2=0;
	P[0]=1;
	comp.pb(0);
	for(int i=1;i<=n;i++)P[i]=(P[i-1]*2LL)%mod;
	for(int i=1;i<=n;i++)cin>>val[i][0];
	for(int i=1;i<=n;i++){
		cin>>val[i][1];
		if(val[i][0]>val[i][1])swap(val[i][0],val[i][1]);
		comp.pb(val[i][0]);
		comp.pb(val[i][1]);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)),comp.end());
	sz=comp.size()-1;
	for(int i=1;i<=n;i++){
		val[i][0]=lb(all(comp),val[i][0])-comp.begin();
		val[i][1]=lb(all(comp),val[i][1])-comp.begin();
	}

	for(int i=1;i<=n;i++){
		for(int k=0;k<2;k++)ans=(ans-(P[n-1]*comp[val[i][k]])%mod+mod)%mod;
	}

	vector<pii>upd;
	int sum2=0;

	t.init();
	t.modify(0,0,1);

	for(int i=1;i<=n;i++)tmx.update(val[i][1],1);
	suf[n+1]=minf;
	pref[0]=minf;
	for(int i=n;i>=1;i--)suf[i]=max(suf[i+1],val[i][0]);
	for(int i=1;i<=n;i++)pref[i]=max(pref[i-1],val[i][0]);
	for(int i=1;i<=n;i++){
		tmx.update(val[i][1],-1);
		for(int k=0;k<2;k++){
			if(suf[i+1]<=val[i][k]-1){
				sum2=P[tmx.qry(val[i][k]-1)];
				ans=(ans+(sum2*(t.getdp(0,val[i][k])+(t.getways(0,val[i][k])*comp[val[i][k]])%mod)%mod)%mod)%mod;
				sub[i][k]=sum2;
			}
		}
		upd.clear();
		for(int k=0;k<2;k++){
			upd.pb({t.getdp(0,val[i][k]-1),t.getways(0,val[i][k]-1)});
		}
		t.update(0,val[i][0]-1,0);
		t.update(val[i][0],val[i][1]-1,1);
		t.update(val[i][1],sz,2);
		for(int k=0;k<2;k++){
			t.modify(val[i][k],(upd[k].f+(comp[val[i][k]]*upd[k].s)%mod)%mod,upd[k].s);
		}
	}
	for(int i=1;i<=n;i++)tmx.update(val[i][1],1);

	t.init();
	t.modify(0,0,1);
	for(int i=n;i>=1;i--){
		//fix left equal
		tmx.update(val[i][1],-1);
		for(int k=0;k<2;k++){
			if(pref[i-1]<=val[i][k]){
				sum2=P[tmx.qry(val[i][k])];
				ans=ans+(sum2*(t.getdp(0,val[i][k]-1)+(t.getways(0,val[i][k]-1)*comp[val[i][k]])%mod)%mod)%mod;
				ans=(ans-((sub[i][k]*sum2)%mod*comp[val[i][k]])%mod+mod)%mod;
			}
		}

		upd.clear();
		for(int k=0;k<2;k++){
			upd.pb({t.getdp(0,val[i][k]-1),t.getways(0,val[i][k]-1)});
		}

		t.update(0,val[i][0]-1,0);
		t.update(val[i][0],val[i][1]-1,1);
		t.update(val[i][1],sz,2);
		for(int k=0;k<2;k++){
			t.modify(val[i][k],(upd[k].f+(comp[val[i][k]]*upd[k].s)%mod)%mod,upd[k].s);
		}
	}
	cout<<ans;
}
/*
*/

Compilation message (stderr)

Main.cpp:12:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   12 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Main.cpp:28:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   28 |         void init(){for(int i=0;i<=4*sz;i++)dp[i]=waysx[i]=ways[i]=0,lazy[i]={1,0};}
      |                   ^
Main.cpp:30:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   30 |         void apply(int pos,pii x){
      |                                 ^
Main.cpp:36:38: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   36 |         void push(int pos,int l,int r){
      |                                      ^
Main.cpp:44:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 |         void pull(int pos){
      |                          ^
Main.cpp:49:67: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 |         void update(int ql,int qr,int k,int pos=1,int l=0,int r=sz){
      |                                                                   ^
Main.cpp:57:68: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   57 |         void modify(int qpos,int d,int w,int pos=1,int l=0,int r=sz){
      |                                                                    ^
Main.cpp:70:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   70 |         int getways(int ql,int qr,int pos=1,int l=0,int r=sz){
      |                                                             ^
Main.cpp:76:59: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   76 |         int getdp(int ql,int qr,int pos=1,int l=0,int r=sz){
      |                                                           ^
Main.cpp:88:19: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   88 |         void init(){for(int i=0;i<=sz+1;i++)fwk[i]=0;}
      |                   ^
Main.cpp:89:36: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   89 |         void update(int pos,int val){
      |                                    ^
Main.cpp:94:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   94 |         int qry(int pos){
      |                        ^
Main.cpp:103:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  103 | int32_t main(){
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...