Submission #359019

#	Time	Username	Problem	Language	Result	Execution time	Memory
359019		jesus_coconut	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	30 ms	6988 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
int const MOD = 1e9 + 7;
int n;
vector<ll> h, w;

void read() {
	cin >> n;
	h.resize(n);
	w.resize(n);
	for (auto &a : h) cin >> a;
	for (auto &a : w) cin >> a;
}

ll modsub(ll a, ll b) {
	ll ret = (a - b) % MOD;
	if (ret < 0) ret += MOD;
	return ret;
}

ll pot(ll a, int k) {
	ll ret = 1;
	while (k) {
		if (k % 2) {
			ret *= a;
			ret %= MOD;
		}
		a *= a;
		a %= MOD;
		k /= 2;
	}
	return ret;
}

void solve() {
	read();
	h.push_back(0);
	w.push_back(0);
	ll ans = 0;
	ll inv2 = pot(2, MOD - 2);
	vector<pair<ll, ll>> stck;
	h.push_back(0);
	w.push_back(0);
	stck.emplace_back(0, 0);
	for (int i = 0; i <= n; ++i) {
		ll sumW = 0;
		while (stck.back().first > h[i]) {
			ll prevH = max(h[i], stck[stck.size() - 2].first);
			ll dH = stck.back().first - prevH;
			sumW = (sumW + stck.back().second) % MOD;
			stck.pop_back();
			ans += (dH * (dH + 1) % MOD * inv2 % MOD + dH * prevH % MOD)
					* (sumW * (sumW + 1) % MOD * inv2 % MOD) % MOD;
			ans %= MOD;
		}
		if (stck.back().first == h[i]) {
			stck.back().second += (sumW + w[i]) % MOD;
			stck.back().second %= MOD;
		} else {
			stck.emplace_back(h[i], (sumW + w[i]) % MOD);
		}
	}
	cout << ans << '\n';
}

int main() {
	//freopen("input1.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}

• 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