Submission #466359

#	Time	Username	Problem	Language	Result	Execution time	Memory
466359		training4usaco	Fancy Fence (CEOI20_fancyfence)	C++11	100 / 100	44 ms	6248 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
 
const int LIM = 1e5+1, MOD = 1e9+7;
 
int n, h[LIM], w[LIM], e[LIM], dp[LIM];
 
int nC2(int x){ return ((x * (x-1)) / 2) % MOD; }
 
int cnt(int x, int y){
	return (nC2(x+1) * nC2(y+1)) % MOD;
}
 
int find(int u){
	return e[u] < 0 ? u : e[u] = find(e[u]);
}
 
void unite(int u, int v, int currH){
	u = find(u), v = find(v);
	if(u != v){
		if(e[u] > e[v]) swap(u, v);
		dp[u] += cnt(w[u], h[u]) - cnt(w[u], currH);
		dp[v] += cnt(w[v], h[v]) - cnt(w[v], currH);
 
		e[u] += e[v], e[v] = u;
		(w[u] += w[v]) %= MOD;
		(dp[u] += dp[v]) %= MOD;
		h[u] = currH;
	}
}
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=1; i<=n; ++i) cin >> h[i];
	for(int i=1; i<=n; ++i) cin >> w[i];
 
	int a[n]; iota(a, a+n, 1);
	sort(a, a+n, [&](int &x, int &y){
		return h[x] > h[y];
	});
	fill(e, e+LIM, -1);
 
	for(int &i : a){
		if(i != 1 && h[find(i-1)] >= h[i]) unite(i, i-1, h[i]);
		if(i != n && h[find(i+1)] >= h[i]) unite(i, i+1, h[i]);
	}
 
	int r = find(1);
	dp[r] += cnt(w[r], h[r]);
	dp[r] %= MOD;
 
	cout << (dp[r] + MOD) % MOD;
 
}

• 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