Submission #945435

#	Time	Username	Problem	Language	Result	Execution time	Memory
945435		amirhoseinfar1385	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	32 ms	8536 KiB

fancyfence

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

void vorod(){
	cin>>n;
	for(long long i=0;i<n;i++){
		cin>>h[i];
	}
	for(long long 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{
	long long par[maxn],res,wh[maxn];
	dsu(){
		res=0;
	}
	void ins(long long u){
		par[u]=u;
		wh[u]=w[u];
		res+=c2(wh[u]+1);
		res%=mod;
	}	
	long long root(long long u){
		if(par[u]==u){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(long long u,long long v){
		long long rootu=root(u),rootv=root(v);
		if(rootu!=rootv){
			par[rootv]=rootu;
			res+=(wh[rootu]%mod)*(wh[rootv]%mod)%mod;
			wh[rootu]+=wh[rootv];
			res%=mod;
		}
	}
}ds;

void solve(){
	vector<pair<long long,long long>>sor;
	for(long long i=0;i<n;i++){
		sor.push_back(make_pair(h[i],i));
	}	
	sort(sor.begin(),sor.end());
	long long last=sor.back().first;
	while((long long)sor.size()>0){
		mainres+=ds.res*((mod+mod+c2(last+1)-c2(sor.back().first+1))%mod)%mod;
		mainres%=mod;
		auto x=sor.back();
	//	cout<<mainres<<" "<<x.first<<" "<<x.second<<" "<<last<<" "<<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;
	}
	//cout<<"wtf: "<<last<<" "<<c2(last+1)<<" "<<ds.res<<endl;
	mainres+=ds.res*(c2(last+1))%mod;
	mainres%=mod;
}

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: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27