제출 #1118436

#제출 시각아이디문제언어결과실행 시간메모리
1118436fryingduc나일강 (IOI24_nile)C++17
100 / 100
90 ms13492 KiB
#include "bits/stdc++.h" using namespace std; #ifdef duc_debug #include "bits/debug.h" #else #include "nile.h" #define debug(...) #endif const int maxn = 1e5 + 5; const int inf = 1e9; int n, q; long long ans; struct info { int w, a, b; } a[maxn]; pair<int, int> que[maxn]; struct dsu { int n; vector<int> left_most; vector<int> lab; vector<int> odd; vector<int> even; vector<int> temp_even, temp_odd; void resize(int &sz) { left_most.resize(sz + 1); even.resize(sz + 1); odd.resize(sz + 1); temp_even.resize(sz + 1); temp_odd.resize(sz + 1); } dsu() {} dsu(int n) : n(n), lab(n + 1, -1) { resize(n); for(int i = 1; i <= n; ++i) { left_most[i] = i; even[i] = inf; temp_even[i] = temp_odd[i] = inf; odd[i] = a[i].a - a[i].b; } } int find(int u) { return lab[u] < 0 ? u : lab[u] = find(lab[u]); } void refine(int u, int v) { if(left_most[u] < left_most[v]) { if(lab[u] & 1) { swap(odd[v], even[v]); swap(temp_odd[v], temp_even[v]); } } else { if(lab[v] & 1) { swap(odd[u], even[u]); swap(temp_odd[u], temp_even[u]); } } } void join(int u, int v) { u = find(u), v = find(v); if(u == v) return; if(lab[u] > lab[v]) swap(u, v); if(lab[u] & 1) { ans -= min(odd[u], temp_even[u]); } if(lab[v] & 1) { ans -= min(odd[v], temp_even[v]); } refine(u, v); even[u] = min(even[u], even[v]); odd[u] = min(odd[u], odd[v]); left_most[u] = min(left_most[u], left_most[v]); temp_odd[u] = min(temp_odd[u], temp_odd[v]); temp_even[u] = min(temp_even[u], temp_even[v]); lab[u] += lab[v]; lab[v] = u; if(lab[u] & 1) { ans += min(odd[u], temp_even[u]); } } void make(int u) { int val = a[u].a - a[u].b; int root = find(u); if((u - left_most[root] + 1) & 1) { temp_odd[root] = min(temp_odd[root], val); } else { if(lab[root] & 1) { ans -= min(odd[root], temp_even[root]); } temp_even[root] = min(temp_even[root], val); if(lab[root] & 1) { ans += min(odd[root], temp_even[root]); } } } } d; vector<long long> solve() { for(int i = 1; i <= n; ++i) { ans += a[i].a; } sort(que + 1, que + q + 1); sort(a + 1, a + n + 1, [](const info &x, const info &y) -> bool { return x.w < y.w; }); vector<pair<int, int>> diff; vector<pair<int, int>> diff_mid; for(int i = 2; i <= n; ++i) { diff.push_back(make_pair(a[i].w - a[i - 1].w, i)); if(i < n) { diff_mid.push_back(make_pair(a[i + 1].w - a[i - 1].w, i)); } } debug(ans); sort(diff.begin(), diff.end(), greater<pair<int, int>>()); sort(diff_mid.begin(), diff_mid.end(), greater<pair<int, int>> ()); d = dsu(n); vector<long long> res(q); for(int i = 1; i <= q; ++i) { while(!diff.empty() and diff.back().first <= que[i].first) { d.join(diff.back().second - 1, diff.back().second); diff.pop_back(); } while(!diff_mid.empty() and diff_mid.back().first <= que[i].first) { d.make(diff_mid.back().second); diff_mid.pop_back(); } res[que[i].second - 1] = ans; } // for(int i = 0; i < q; ++i) { // cout << res[i] << '\n'; // } return res; } vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { n = (int)W.size(); for(int i = 0; i < n; ++i) { a[i + 1].w = W[i]; a[i + 1].a = A[i]; a[i + 1].b = B[i]; } q = (int)E.size(); for(int i = 0; i < q; ++i) { que[i + 1] = make_pair(E[i], i + 1); } return solve(); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...