제출 #1191332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191332		8pete8	Flooding Wall (BOI24_wall)	C++20	70 / 100	5099 ms	103776 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sz(x) (int)((x).size())
//#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6,inf=1e18,minf=-1e18,lg=30,Mxn=1e9;
//#undef int
int n,k,m,d,q,X,W,T;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int val[mxn+10][2];
int P[mxn+10],sub[mxn+10][2];
int add(int x,int a){
	return 1LL*(x+(ll)a+mod)%mod;
}
int mul(int x,int a){return (1LL*x*a)%mod;}

vector<int>comp;
struct seg{
	int dp[4*mxn+10],sum[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*comp.size();i++)dp[i]=sum[i]=waysx[i]=ways[i]=0,lazy[i]={1,0};}
	pii merge(pii a,pii b){return {mul(a.f,b.f),add(mul(a.s,b.f),mul(a.f,b.s))};}
	void apply(int pos,pii x){
		dp[pos]=add(mul(x.f,dp[pos]),mul(x.s,waysx[pos]));
		waysx[pos]=mul(x.f,waysx[pos]);
		ways[pos]=mul(x.f,ways[pos]);
		lazy[pos]=merge(lazy[pos],x);
	}
	void push(int pos,int l,int r){
		if(l!=r){
			apply(pos<<1,lazy[pos]);
			apply(pos<<1|1,lazy[pos]);
		}
		lazy[pos]={1,0};
	}
	void pull(int pos){
		dp[pos]=add(dp[pos<<1],dp[pos<<1|1]);
		sum[pos]=add(sum[pos<<1],sum[pos<<1|1]);
		waysx[pos]=add(waysx[pos<<1],waysx[pos<<1|1]);
		ways[pos]=add(ways[pos<<1],ways[pos<<1|1]);
	}
	void update(int ql,int qr,int k,int pos=1,int l=0,int r=comp.size()){
		if(l>qr||r<ql)return;
		if(ql<=l&&r<=qr)return void(apply(pos,{k,k}));
		int mid=l+(r-l)/2;
		push(pos,l,r);
		update(ql,qr,k,pos<<1,l,mid);
		update(ql,qr,k,pos<<1|1,mid+1,r);
		pull(pos);
	}
	void modify(int qpos,int d,int w,int pos=1,int l=0,int r=comp.size()){
		if(l>qpos||r<qpos)return;
		if(l==r){
			dp[pos]=add(dp[pos],d);
			ways[pos]=add(ways[pos],w);
			waysx[pos]=add(waysx[pos],mul(w,comp[l]));
			return;
		}
		int mid=l+(r-l)/2;
		push(pos,l,r);
		modify(qpos,d,w,pos<<1,l,mid);
		modify(qpos,d,w,pos<<1|1,mid+1,r);
		pull(pos);
	}
	int getways(int ql,int qr,int pos=1,int l=0,int r=comp.size()){
		if(l>qr||r<ql)return 0;
		if(ql<=l&&r<=qr)return ways[pos];
		int mid=l+(r-l)/2;
		push(pos,l,r);
		return add(getways(ql,qr,pos<<1,l,mid),getways(ql,qr,pos<<1|1,mid+1,r));
	}
	int getdp(int ql,int qr,int pos=1,int l=0,int r=comp.size()){
		if(l>qr||r<ql)return 0;
		if(ql<=l&&r<=qr)return dp[pos];
		int mid=l+(r-l)/2;
		push(pos,l,r);
		return add(getdp(ql,qr,pos<<1,l,mid),getdp(ql,qr,pos<<1|1,mid+1,r));
	}
}t;

struct fen{
	int fwk[mxn+10];
	void init(){for(int i=0;i<=comp.size();i++)fwk[i]=0;}
	void update(int pos,int val){
		pos++;
		for(int i=pos;i<=comp.size();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;
	}
	int get(int l,int r){
		return qry(r)-qry(l-1);
	}
}tmx,tmn;

int32_t main(){
	fastio
	cin>>n;
	int mx=0,ans=0;
	P[0]=1;
	
	comp.pb(0);
	for(int i=1;i<=n;i++)P[i]=mul(P[i-1],2LL);
	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());
	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=add(ans,-mul(P[n-1],comp[val[i][k]]));
	}

	vector<pii>upd;
	t.init();
	t.modify(0,0,1);
	for(int i=1;i<=n;i++)tmx.update(val[i][1],1),tmn.update(val[i][0],1);

	for(int i=1;i<=n;i++){
		tmx.update(val[i][1],-1);
		tmn.update(val[i][0],-1);
		for(int k=0;k<2;k++){
			int sumd=0,sumw=0,sum2=0;
			
			if(tmn.qry(val[i][k]-1)==n-i)sum2=P[tmx.qry(val[i][k]-1)];
			sumd=t.getdp(0,val[i][k]);
			sumw=t.getways(0,val[i][k]);
			sub[i][k]=sum2;
			int x=add(sumd,mul(sumw,comp[val[i][k]]));
			ans=add(ans,mul(x,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],comp.size()-1,2);
		for(int k=0;k<2;k++){
			t.modify(val[i][k],add(upd[k].f,mul(comp[val[i][k]],upd[k].s)),upd[k].s);
		}
	}
	for(int i=1;i<=n;i++)tmx.update(val[i][1],1),tmn.update(val[i][0],1);
	t.init();
	t.modify(0,0,1);
	for(int i=n;i>=1;i--){
		//fix left equal
		tmx.update(val[i][1],-1);
		tmn.update(val[i][0],-1);
		for(int k=0;k<2;k++){
			int sumd=0,sumw=0,sum2=0;


			if(tmn.qry(val[i][k])==i-1)sum2=P[tmx.qry(val[i][k])];

			sumd=t.getdp(0,val[i][k]-1);
			sumw=t.getways(0,val[i][k]-1);

			int x=add(sumd,mul(sumw,comp[val[i][k]]));
			ans=add(ans,mul(x,sum2));
			ans=add(ans,-mul(comp[val[i][k]],mul(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],comp.size()-1,2);
		for(int k=0;k<2;k++){
			t.modify(val[i][k],add(upd[k].f,mul(comp[val[i][k]],upd[k].s)),upd[k].s);
		}
	}
	cout<<ans;

}
/*
*/

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:22:33: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int mod=1e9+7,mxn=1e6,inf=1e18,minf=-1e18,lg=30,Mxn=1e9;
      |                                 ^~~~
Main.cpp:22:43: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   22 | const int mod=1e9+7,mxn=1e6,inf=1e18,minf=-1e18,lg=30,Mxn=1e9;
      |                                           ^~~~~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:27:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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