oj.uz

Submission #359023

# Submission time Handle Problem Language Result Execution time Memory
359023 2021-01-26T09:10:59 Z jesus_coconut Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 512 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct