Submission #448581

#TimeUsernameProblemLanguageResultExecution timeMemory
448581ritul_kr_singhFancy Fence (CEOI20_fancyfence)C++17
100 / 100
43 ms6340 KiB
#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;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...