Submission #650249

#TimeUsernameProblemLanguageResultExecution timeMemory
650249alvinpiterFancy Fence (CEOI20_fancyfence)C++17
15 / 100
89 ms4796 KiB
#include<bits/stdc++.h> using namespace std; #define LL long long int #define MOD 1000000007 #define MAXN 100000 int n; LL h[MAXN + 3], w[MAXN + 3], sumWidth[MAXN + 3], sumFhw = 0, ans = 0; stack<int> st; LL f(LL k) { LL k1 = k + 1; return k%2 == 0 ? ((k/2)%MOD * (k1)%MOD)%MOD : (k%MOD * (k1/2)%MOD)%MOD; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i]; } sumWidth[0] = 0; for (int i = 1; i <= n; i++) { cin >> w[i]; sumWidth[i] = sumWidth[i - 1] + w[i]; } for (int i = 1; i <= n; i++) { LL rectanglesOnTheCurrentFence = (f(h[i]) * f(w[i]))%MOD; ans = (ans + rectanglesOnTheCurrentFence)%MOD; while (!st.empty() && h[st.top()] >= h[i]) { LL fhw = (f(h[st.top()]) * w[st.top()])%MOD; sumFhw = (sumFhw - fhw + MOD)%MOD; st.pop(); } int firstLowerIdx = (st.empty() ? 0 : st.top()); LL rectanglesOnTheCurrentFenceAndTallerNeighbors = 0; if (firstLowerIdx != i - 1) { rectanglesOnTheCurrentFenceAndTallerNeighbors = (((sumWidth[i - 1] - sumWidth[firstLowerIdx])%MOD * w[i])%MOD * f(h[i]))%MOD; ans = (ans + rectanglesOnTheCurrentFenceAndTallerNeighbors)%MOD; } LL rectanglesOnTheCurrentFenceAndLowerNeighbors = (sumFhw * w[i])%MOD; ans = (ans + rectanglesOnTheCurrentFenceAndLowerNeighbors)%MOD; st.push(i); sumFhw = (sumFhw + (f(h[i]) * w[i])%MOD)%MOD; } cout << ans << endl; }
#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...