Submission #359023

#	Time	Username	Problem	Language	Result	Execution time	Memory
359023		jesus_coconut	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	1 ms	512 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 subRec(int i) {
	ll ret = h[i] * (h[i] + 1) / 2;
	ret %= MOD;
	ret *= (w[i] * (w[i] + 1) / 2) % MOD;
	ret %= MOD;
	return ret;
}

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

ll calc(pair<ll, ll> p) {
	ll ret = (p.first * p.first) % MOD;
	ret *= p.second;
	ret %= MOD;
	return ret;
}

void solve() {
	read();
	ll ans = 0;
	ll carry = 0;
	stack<pair<ll, ll>> stck;
	for (int i = 0; i < n; ++i) {
		ans += subRec(i);
		ans %= MOD;

		ll pushDown = 0;
		while (!stck.empty() && stck.top().first > h[i]) {
			carry = modsub(carry,  calc(stck.top()));
			pushDown += stck.top().second;
			pushDown %= MOD;
			stck.pop();
		}
		if (!stck.empty()) {
			carry = modsub(carry, calc(stck.top()));
			stck.top().second += pushDown;
			stck.top().second %= MOD;
			carry += calc(stck.top());
			carry %= MOD;
		}
		ans += (carry * w[i]) % MOD;
		ans %= MOD;

		stck.emplace(h[i], w[i]);
		carry += calc(stck.top());
		carry %= 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: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27