Submission #1256349

#TimeUsernameProblemLanguageResultExecution timeMemory
1256349pastaFancy Fence (CEOI20_fancyfence)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int maxn = 1e5 + 10; const int mod = 1e9 + 7; int n, L[maxn], dp[maxn], h[maxn], w[maxn], ps[maxn]; int C(int a) { return 1ll * a * (a - 1) % mod; } signed main() { cin >> n; for (int i = 1; i <= n; i++) cin >> h[i] >> w[i]; stack<int> st; for (int i = 1; i <= n; i++) { while (!st.empty() && h[st.top()] >= h[i]) st.pop(); L[i] = 0; if (!st.empty()) L[i] = st.top(); st.push(i); } for (int i = 1; i <= n; i++) { ps[i] = ps[i - 1] + w[i]; ps[i] %= mod; } ll ans = 0; for (int i = 1; i <= n; i++) { dp[i] = dp[L[i]] + (1ll * C(h[i] + 1) * ((ps[i] - ps[L[i]] + mod) % mod) % mod) % mod; ans += dp[i]; ans %= mod; dp[i] %= mod; } cout << ans << '\n'; }
#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...