Submission #987867

#TimeUsernameProblemLanguageResultExecution timeMemory
987867VMaksimoski008Fancy Fence (CEOI20_fancyfence)C++17
100 / 100
110 ms9036 KiB
#include <bits/stdc++.h> #define int long long using namespace std; using ll = long long; const int mod = 1e9 + 7; ll exp(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = (ans * a) % mod; a = (a * a) % mod; b /= 2; } return ans; } ll inv(ll a) { return exp(a, mod - 2); } ll C(ll a) { return a * (a + 1) % mod * inv(2) % mod; } ll S(ll l, ll r) { return (C(r%mod) - C((l-1+mod)%mod) + mod) % mod; } struct DSU { int n, comp; vector<int> par, size, W; void config(int _n) { n = _n + 1; comp = _n; par.resize(n+1); size.resize(n+1, 1); W.resize(n+1); for(int i=1; i<=n; i++) par[i] = i; } int get(int u) { if(u == par[u]) return u; return par[u] = get(par[u]); } bool uni(int u, int v) { u = get(u), v = get(v); if(u == v) return 0; if(size[u] < size[v]) swap(u, v); size[u] += size[v]; W[u] = (W[u] + W[v]) % mod; par[v] = u; return 1; } void setW(int p, int w) { W[get(p)] += w; } ll getW(int p) { return W[get(p)]; } }; struct Edge { int a, b, w; bool operator<(Edge &e) { return w > e.w;} }; int32_t main() { int n; cin >> n; vector<ll> h(n+1), w(n+1); for(int i=1; i<=n; i++) cin >> h[i]; for(int i=1; i<=n; i++) cin >> w[i]; ll ans = 0; for(int i=1; i<=n; i++) ans = (ans + C(w[i]) * C(h[i])) % mod; DSU dsu; dsu.config(n); for(int i=1; i<=n; i++) dsu.setW(i, w[i]); vector<Edge> edges; for(int i=1; i<n; i++) edges.push_back({ i, i + 1, min(h[i], h[i+1]) }); sort(edges.begin(), edges.end()); for(Edge &e : edges) { ll L = dsu.getW(e.a), R = dsu.getW(e.b); dsu.uni(e.a, e.b); ans = (ans + (R + mod) % mod * C(e.w) % mod * (L + mod) % mod) % mod; } cout << ans << '\n'; 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...