Submission #609297

#TimeUsernameProblemLanguageResultExecution timeMemory
6092971binFancy Fence (CEOI20_fancyfence)C++14
100 / 100
30 ms4180 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e5 + 5; const ll mod = 1e9 + 7; ll n, h[NMAX], w[NMAX], ans, x, ix, mxh, wd; stack<int> st; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i++) cin >> h[i]; for(int i = 1; i <= n; i++) cin >> w[i], w[i] = (w[i] + w[i - 1]) % mod; st.emplace(0); for(int i = 1; i <= n; i++){ while(st.size() >= 2 && h[st.top()] > h[i]){ ix = st.top(); st.pop(); mxh = max(h[st.top()], h[i]); wd = w[ix] - w[st.top()]; wd = (wd % mod + mod) % mod; ans += (h[ix] * (h[ix] + 1) / 2 - mxh * (mxh + 1) / 2) % mod * (wd * (wd + 1) / 2 % mod); ans %= mod; if(h[st.top()] > h[i]) w[st.top()] = w[ix]; } if(h[st.top()] == h[i]) st.pop(); st.emplace(i); } while(st.size() >= 2){ ix = st.top(); st.pop(); wd = w[n] - w[st.top()]; wd = (wd % mod + mod) % mod; ans += (h[ix] * (h[ix] + 1) / 2 - h[st.top()] * (h[st.top()] + 1) / 2) % mod * (wd * (wd + 1) / 2 % mod); ans %= mod; } cout << ans; return 0; }
#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...