Submission #1013111

#TimeUsernameProblemLanguageResultExecution timeMemory
1013111Gromp15Fancy Fence (CEOI20_fancyfence)C++17
100 / 100
18 ms3940 KiB
#include <bits/stdc++.h> #define ll long long #define ar array #define db double #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rint(l, r) uniform_int_distribution<int>(l, r)(rng) template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } const int mod = 1e9+7, nax = 1e5 + 5; int tp = -1; ar<int, 2> stk[nax]; int f(int x) { return ((ll)x*(x+1)/2)%mod; } int mul(int a, int b) { return (ll)a*b%mod; } void fadd(int &a, int b) { a += b; if (a >= mod) a -= mod; } void fsub(int &a, int b) { a -= b; if (a < 0) a += mod; } void test_case() { int n; cin >> n; vector<int> h(n), w(n); for (int &x : h) cin >> x; for (int &x : w) cin >> x; int ans = 0, t = 0; for (int i = 0; i < n; i++) { fadd(ans, mul(f(h[i]), f(w[i]))); int L = 0; while (tp >= 0 && stk[tp][0] >= h[i]) { fsub(t, mul(f(stk[tp][0]), stk[tp][1])); fadd(L, stk[tp][1]); tp--; } fadd(ans, mul(t, w[i])); fadd(ans, mul(mul(f(h[i]), L), w[i])); fadd(L, w[i]); stk[++tp] = {h[i], L}; fadd(t, mul(f(h[i]), L)); } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while (t--) test_case(); }
#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...