Submission #719076

#	Time	Username	Problem	Language	Result	Execution time	Memory
719076		esomer	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	44 ms	6004 KiB

fancyfence

#include<bits/stdc++.h>
 
using namespace std;
 
#define endl "\n"

typedef long long int ll;
 
const int MOD = 1e9 + 7;

struct DSU{
	vector<int> v;
	vector<ll> sum;
	void init(vector<tuple<ll, ll, int>>& a){
		int n = (int)a.size();
		v.assign(n, -1);
		sum.assign(n, 0);
		for(int i = 0; i < n; i++){
			sum[get<2>(a[i])] = get<1>(a[i]);
		}
	}
	int gt(int x){return v[x] < 0 ? x : v[x] = gt(v[x]);}
	ll gets(int x){return sum[gt(x)] % MOD;}
	void unite(int x, int y){
		x = gt(x); y = gt(y);
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x; sum[x] += sum[y]; sum[x] %= MOD;
	}
};

ll calc(ll x){
	if(x % 2 == 0){
		ll f = x / 2; f %= MOD;
		ll s = x - 1; s %= MOD;
		return (f * s) % MOD;
	}else{
		ll f = x; f %= MOD;
		ll s = (x - 1) / 2; s %= MOD;
		return (f * s) % MOD;
	}
}

ll self(ll w, ll h){
	w++; h++;
	return (calc(w) * calc(h)) % MOD;
}

ll two(ll w, ll h, ll w1, ll h1){
	h++;
	ll x = w * w1; x %= MOD;
	return (x * calc(h)) % MOD;
}

void solve(){
	int n; cin >> n;
	vector<tuple<ll, ll, int>> v(n);
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		get<0>(v[i]) = x;
	}
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		get<1>(v[i]) = x;
		get<2>(v[i]) = i;
	}
	sort(v.begin(), v.end());
	if(n == 1){
		ll w = get<1>(v[0]);
		ll h = get<0>(v[0]);
		cout << self(w, h) << endl;
		return;
	}
	DSU UF; UF.init(v);
	vector<bool> done(n, 0);
	ll ans = 0;
	for(int i = n - 1; i >= 0; i--){
		int j = get<2>(v[i]);
		ll w = get<1>(v[i]);
		ll h = get<0>(v[i]);
		done[j] = 1;
		ans += self(w, h); ans %= MOD;
		if(j == 0){
			if(done[1]){
				ans += two(w, h, UF.gets(1), h); ans %= MOD;
				UF.unite(0, 1);
			}
		}else if(j == n - 1){
			if(done[n-2]){
				ans += two(w, h, UF.gets(n-2), h); ans %= MOD;
				UF.unite(j, n-2);
			}
		}else{
			if(done[j+1]){
				ans += two(w, h, UF.gets(j+1), h); ans %= MOD;
				if(done[j-1]){
					ans += two(w, h, UF.gets(j-1), h); ans %= MOD;
					ans += two(UF.gets(j+1), h, UF.gets(j-1), h); ans %= MOD;
					UF.unite(j-1, j);
				}
				UF.unite(j+1, j);
			}else if(done[j-1]){
				ans += two(w, h, UF.gets(j-1), h); ans %= MOD;
				UF.unite(j-1, j);
			}
		}
	}
	cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //~ int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        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