제출 #987863

#제출 시각아이디문제언어결과실행 시간메모리
987863VMaksimoski008Fancy Fence (CEOI20_fancyfence)C++17
25 / 100
54 ms6388 KiB
#include <bits/stdc++.h> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() //#define int long long using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const double eps = 1e-9; 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; vector<ll> 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 false; if(size[u] < size[v]) swap(u, v); size[u] += size[v]; W[u] = (W[u] + W[v]) % mod; par[v] = u; comp--; return true; } int getComp() { return comp; } int getSize(int u) { return size[get(u)]; } bool sameSet(int u, int v) { return get(u) == get(v); } 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() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); 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]; //gl&hf 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(all(edges)); for(Edge &e : edges) { ll L = dsu.getW(e.a); ll R = dsu.getW(e.b); dsu.uni(e.a, e.b); ll T = dsu.getW(e.a); ans = (ans + R * C(e.w) * L % mod) % mod; } cout << ans << '\n'; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

fancyfence.cpp: In function 'int32_t main()':
fancyfence.cpp:100:59: warning: narrowing conversion of '(long long int)std::min<long long int>((*(const long long int*)(& h.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)i)))), (*(const long long int*)(& h.std::vector<long long int>::operator[](((std::vector<long long int>::size_type)(i + 1))))))' from 'long long int' to 'int' [-Wnarrowing]
  100 |     for(int i=1; i<n; i++) edges.push_back({ i, i + 1, min(h[i], h[i+1]) });
      |                                                        ~~~^~~~~~~~~~~~~~
fancyfence.cpp:107:12: warning: unused variable 'T' [-Wunused-variable]
  107 |         ll T = dsu.getW(e.a);
      |            ^
#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...