Submission #963008

#TimeUsernameProblemLanguageResultExecution timeMemory
963008zwezdinvFancy Fence (CEOI20_fancyfence)C++17
100 / 100
33 ms4320 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; int mod = 1e9 + 7; int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; } int sub(int a, int b) { return a >= b ? a - b : a + mod - b; } int mul(int a, int b) { return 1ll * a * b % mod; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int i2 = (mod + 1) / 2; auto sshit = [&](int x) -> int { return mul(mul(x, x + 1), i2); }; int n; cin >> n; vector<pair<int, int>> st; vector<int> h(n), w(n); for (auto& i : h) cin >> i; for (auto& i : w) cin >> i; int sum = 0; int ans = 0; for (int i = 0; i < n; ++i) { int cnt = w[i]; while (st.size() && st.back().first >= h[i]) { cnt = add(cnt, st.back().second); sum = sub(sum, mul(sshit(st.back().first), st.back().second)); st.pop_back(); } st.emplace_back(h[i], cnt); sum = add(sum, mul(sshit(h[i]), cnt)); int cur = mul(sum, w[i]); cur = sub(cur, mul(sshit(h[i]), mul(w[i], w[i]))); cur = add(cur, mul(sshit(w[i]), sshit(h[i]))); ans = add(ans, cur); } cout << ans; }
#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...