Submission #997763

#TimeUsernameProblemLanguageResultExecution timeMemory
997763RaresFelixFancy Fence (CEOI20_fancyfence)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define int ll using ll = long long; using vi = vector<int>; using ii = pair<int, int>; const int MOD = 1e9 + 7; const int inv2 = 5e8 + 4; struct DSU { int re = 0; vi e, s; DSU(int n, const vi &S0) : e(n, -1), s(S0) {} int repr(int u) { while(e[u] >= 0) u = e[u]; return u; } void join(int u, int v) { u = repr(u); v = repr(v); if(u == v) return; if(e[u] > e[v]) swap(u, v); e[u] += e[v]; e[v] = u; re = (re - 1ll * s[u] * (s[u] + 1) % MOD * int(5e8 + 4) % MOD) % MOD; re = (re - 1ll * s[v] * (s[v] + 1) % MOD * int(5e8 + 4) % MOD) % MOD; s[u] += s[v]; re = (re + 1ll * s[u] * (s[u] + 1) % MOD * int(5e8 + 4) % MOD) % MOD; re = (re + MOD) % MOD; } }; signed main() { int n; cin >> n; vi W(n); vector<ii> H(n); for(int i = 0; i < n; ++i) { cin >> H[i].first; H[i].second = i; } for(int i = 0; i < n; ++i) cin >> W[i]; DSU Sol(n, W); vi on(n, 0); sort(H.begin(), H.end()); ll s = 0, ant = 0; ll re = 0, hant = 0; for(int i = 0; i < n; ++i) { int dr = i; do { s += 1ll * W[dr] * (W[dr] + 1) % MOD * inv2 % MOD; int p = H[dr].second; on[p] = 1; if(p && on[p - 1]) Sol.join(p, p - 1); if(p + 1 < n && on[p + 1]) Sol.join(p, p + 1); ++dr; } while(dr < n && H[dr].first == H[dr - 1].first); ll cur = (s + Sol.re) % MOD * H[i].first % MOD; cur = (cur % MOD + MOD) % MOD; ll delta = cur - ant; delta = (delta % MOD + MOD) % MOD; ant = cur; re = (re + delta % MOD) % MOD; i = dr - 1; } cout << re << "\n"; return 0; }

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:54:16: warning: unused variable 'hant' [-Wunused-variable]
   54 |     ll re = 0, hant = 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...