Submission #1241770

#TimeUsernameProblemLanguageResultExecution timeMemory
1241770acoatoitgs나일강 (IOI24_nile)C++20
38 / 100
256 ms96324 KiB
#include "nile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pi = pair<ll,ll>; #define all(x) (x).begin(),(x).end() vector<int> W, A, B, E; vector<ll> P, R; vector<pi> queries, V, merges; int N, Q; ll ans = 0; priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll>>, greater<tuple<ll,ll,ll>>> removals; struct group { ll l, r; bool in_use; multiset<pi> usable; group() {} void init(ll idx) { l = r = idx; in_use = 1; usable.insert({A[V[r].second] - B[V[r].second], l}); if(l != 0 && r != N-1) { removals.push({V[r+1].first - V[r-1].first, A[V[r].second] - B[V[r].second], l}); } } }; vector<group> gr; ll fp(ll pos) { return (P[pos] == pos ? pos : P[pos] = fp(P[pos])); } vector<long long> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) { W = w; A = a; B = b; E = e; N = W.size(); Q = E.size(); R.resize(Q, 0); P.resize(N); gr.resize(N); iota(all(P), 0); queries.clear(); for(ll q = 0; q < Q; q++) queries.emplace_back(E[q], q); V.clear(); for(ll i = 0; i < N; i++) V.emplace_back(W[i], i), ans += A[i]; sort(all(V)); sort(all(queries)); while (!removals.empty()) removals.pop(); merges.clear(); for(ll i = 0; i < N; i++) gr[i].init(i); for(ll i = 0; i < N-1; i++) merges.emplace_back(V[i+1].first - V[i].first, i); sort(all(merges), greater<pi>()); for(auto [D, q] : queries) { while(!removals.empty()) { auto top = removals.top(); ll len = get<0>(top); ll delta = get<1>(top); ll idx = get<2>(top); if (len > D) break; removals.pop(); ll p = fp(idx); if(gr[p].in_use) { ans -= (*gr[p].usable.begin()).first; } gr[p].usable.insert({delta, idx}); if(gr[p].in_use) { ans += (*gr[p].usable.begin()).first; } } while(!merges.empty() && merges.back().first <= D) { ll idx_merge = merges.back().second; ll lg = fp(idx_merge); ll rg = fp(idx_merge+1); if (lg == rg) { merges.pop_back(); continue; } if(gr[lg].in_use) { ans -= (*gr[lg].usable.begin()).first; gr[lg].in_use = 0; } if(gr[rg].in_use) { ans -= (*gr[rg].usable.begin()).first; gr[rg].in_use = 0; } if(gr[lg].usable.size() > gr[rg].usable.size()) { P[rg] = lg; for(auto e : gr[rg].usable) gr[lg].usable.insert(e); if(gr[lg].r != gr[lg].l) { if (V[gr[lg].r].first - V[gr[lg].r-1].first > D) { auto it = gr[lg].usable.find({A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r}); if (it != gr[lg].usable.end()) { gr[lg].usable.erase(it); } } } if(gr[rg].r != gr[rg].l) { if (V[gr[rg].l+1].first - V[gr[rg].l].first > D) { auto it = gr[lg].usable.find({A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l}); if (it != gr[lg].usable.end()) { gr[lg].usable.erase(it); } } } gr[lg].r = gr[rg].r; if(gr[lg].r - gr[lg].l + 1 > 1 && (gr[lg].r - gr[lg].l) % 2 == 0) { ans += (*gr[lg].usable.begin()).first; gr[lg].in_use = 1; } } else { P[lg] = rg; for(auto e : gr[lg].usable) gr[rg].usable.insert(e); if(gr[lg].r != gr[lg].l) { if (V[gr[lg].r].first - V[gr[lg].r-1].first > D) { auto it = gr[rg].usable.find({A[V[gr[lg].r].second] - B[V[gr[lg].r].second], gr[lg].r}); if (it != gr[rg].usable.end()) { gr[rg].usable.erase(it); } } } if(gr[rg].r != gr[rg].l) { if (V[gr[rg].l+1].first - V[gr[rg].l].first > D) { auto it = gr[rg].usable.find({A[V[gr[rg].l].second] - B[V[gr[rg].l].second], gr[rg].l}); if (it != gr[rg].usable.end()) { gr[rg].usable.erase(it); } } } gr[rg].l = gr[lg].l; if(gr[rg].r - gr[rg].l + 1 > 1 && (gr[rg].r - gr[rg].l) % 2 == 0) { ans += (*gr[rg].usable.begin()).first; gr[rg].in_use = 1; } } merges.pop_back(); } R[q] = ans; } return R; }
#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...