Submission #960029

#	Time	Username	Problem	Language	Result	Execution time	Memory
960029		Huseyn123	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	87 ms	9220 KiB

fancyfence

#include <bits/stdc++.h> 
#define MAX 100001
#define MOD 1000000007
using namespace std; 
typedef long long ll;
ll n,x,y,z,w[MAX],h[MAX],a[MAX];
struct DSU{
	vector<int> e;
	DSU(int N){e.resize(N+1,-1);}
	int get(int x){return (e[x]<0) ? x : e[x]=get(e[x]);}
	int size(int x){return w[get(x)];}
	bool unite(int x,int y){
		x=get(x);
		y=get(y);
		if(x==y) return false; 
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y]; w[x]+=w[y]; w[x]%=MOD; e[y]=x;
		return true;
	}
};
ll powmod(ll x,ll y,ll mod){
	if(y==0){
		return 1;
	}
	ll res=1;
	x%=mod;
	while(y>0){
		if(y%2){
			res*=x;
			res%=mod;
		}
		y/=2;
		x*=x;
		x%=mod;
	}
	return res;
}
ll inv(ll n,ll mod){
	return powmod(n,mod-2,mod);
}
ll mul(ll x,ll y){
	return (x*y)%MOD;
}
ll f(ll W,ll H){
	ll res=1;
	res=mul(res,W);
	res=mul(res,W+1);
	res=mul(res,H);
	res=mul(res,H+1);
	res=mul(res,z);
	return res;
}
void solve(){
	cin >> n; 
	z=inv(4,MOD);
	for(int i=0;i<n;i++){
		cin >> h[i];
	}
	for(int i=0;i<n;i++){
		cin >> w[i];
	}
	vector<array<ll,3>> c;
	for(int i=0;i<n;i++){
		c.push_back({h[i],w[i],(ll)i});
	}
	sort(c.rbegin(),c.rend());
	ll res=0;
	DSU dsu(n);
	for(auto x:c){
		ll cnt=x[1];
		a[x[2]]=1;
		if(x[2]-1>=0 && a[x[2]-1]){
			y=dsu.size(x[2]-1);
			res-=f(y,x[0]);
			res=(res+MOD)%MOD;
			cnt+=y;
			cnt%=MOD;
			dsu.unite(x[2],x[2]-1);
		}
		if(x[2]+1<n && a[x[2]+1]){
			y=dsu.size(x[2]+1);
			res-=f(y,x[0]);
			res=(res+MOD)%MOD;
			cnt+=y;
			cnt%=MOD;
			dsu.unite(x[2],x[2]+1);
		}
		res+=f(cnt,x[0]);
		res%=MOD;
	}
	cout << res << "\n";
}
int main(){
	//freopen("input1.txt","r",stdin);
	solve();
}

• 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