Submission #945423

#	Time	Username	Problem	Language	Result	Execution time	Memory
945423		amirhoseinfar1385	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	2 ms	532 KiB

fancyfence

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
int h[maxn],w[maxn],n,vis[maxn],mod=1e9+7;

void vorod(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	for(int i=0;i<n;i++){
		cin>>w[i];
	}
}
long long mainres=0;

long long mypow(long long m,long long y){
	if(y==0){
		return 1;
	}
	long long p=mypow(m,(y>>1));
	p*=p;
	p%=mod;
	if(y&1){
		p*=m;
		p%=mod;
	}
	return p;
}

long long c2(long long a){
	return (a*(a-1)/2)%mod;
}

struct dsu{
	int par[maxn],res,wh[maxn];
	dsu(){
		res=1;
	}
	void ins(int u){
		par[u]=u;
		wh[u]=w[u];
		res*=c2(w[u]+1);
		res%=mod;
	}	
	int root(int u){
		if(par[u]==u){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(int u,int v){
		int rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			par[rootu]=rootv;
			res*=mypow(c2(wh[rootu]+1),mod-2);
			res%=mod;
			res*=mypow(c2(wh[rootv]+1),mod-2);
			res%=mod;
			wh[rootu]+=wh[rootv];
			res*=c2(wh[rootu]+1);
			res%=mod;
		}
	}
}ds;

void solve(){
	vector<pair<int,int>>sor;
	for(int i=0;i<n;i++){
		sor.push_back(make_pair(h[i],i));
	}	
	sort(sor.begin(),sor.end());
	int last=sor.back().first;
	while((int)sor.size()>0){
		mainres+=ds.res*(c2(last+1)-c2(sor.back().first+1));
		auto x=sor.back();
	//	cout<<x.first<<" "<<x.second<<" "<<w[x.second]<<" "<<ds.res<<endl;
		sor.pop_back();
		vis[x.second]=1;
		ds.ins(x.second);
		if(vis[x.second+1]==1){
			ds.con(x.second,x.second+1);
		}
		if(vis[x.second-1]==1){
			ds.con(x.second,x.second-1);
		}
		last=x.first;
	}
	mainres+=ds.res*(c2(last+1));
}

void khor(){
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	solve();
	khor();
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27