Submission #1200668

#TimeUsernameProblemLanguageResultExecution timeMemory
1200668PacybwoahNile (IOI24_nile)C++20
100 / 100
294 ms21936 KiB
#include "nile.h" #include<iostream> #include<algorithm> #include<utility> #include<map> #include<vector> using namespace std; typedef long long ll; namespace{ const ll inf = 2e18; } std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) { int n = (int)W.size(); int q = (int)E.size(); vector<ll> ans(q); ll base = 0; for(int i = 0; i < n; i++) base += B[i]; vector<pair<int, ll>> vec(n + 1); for(int i = 0; i < n; i++) vec[i + 1] = make_pair(W[i], A[i] - B[i]); sort(next(vec.begin()), vec.end()); map<int, pair<pair<ll, ll>, pair<ll, ll>>> m; // odd-all even-all odd-active even-active m[n + 1] = make_pair(make_pair(0, 0), make_pair(0, 0)); for(int i = 1; i <= n; i++){ if(i & 1){ m[i] = make_pair(make_pair(vec[i].second, inf), make_pair(inf, inf)); } else{ m[i] = make_pair(make_pair(inf, vec[i].second), make_pair(inf, inf)); } } vector<pair<ll, pair<int, int>>> ops; ll cur = 0; for(int i = 1; i <= n; i++) cur += vec[i].second; // 0: merge // 1: add element // 2: answer query for(int i = 0; i < q; i++){ ops.emplace_back(E[i], make_pair(2, i)); } for(int i = 1; i < n; i++){ ops.emplace_back(vec[i + 1].first - vec[i].first, make_pair(0, i)); } for(int i = 2; i < n; i++){ ops.emplace_back(vec[i + 1].first - vec[i - 1].first, make_pair(1, i)); } sort(ops.begin(), ops.end()); auto calc = [&](int pos){ int l = pos, r = (*m.upper_bound(pos)).first - 1; int len = r - l + 1; if(len & 1){ if(l & 1) return min(m[pos].first.first, m[pos].second.second); else return min(m[pos].first.second, m[pos].second.first); } else return 0ll; }; auto unite = [&](int pos){ // merge comp(pos) and comp(pos + 1) int l = (*prev(m.upper_bound(pos))).first, r = (*prev(m.upper_bound(pos + 1))).first; cur -= calc(l); cur -= calc(r); m[l].first.first = min(m[l].first.first, m[r].first.first); m[l].first.second = min(m[l].first.second, m[r].first.second); m[l].second.first = min(m[l].second.first, m[r].second.first); m[l].second.second = min(m[l].second.second, m[r].second.second); m.erase(m.find(r)); cur += calc(l); return; }; for(auto &[day, info]: ops){ auto &[tp, id] = info; if(tp == 0){ unite(id); } else if(tp == 1){ int mum = (*prev(m.upper_bound(id))).first; cur -= calc(mum); if(id & 1){ m[mum].second.first = min(m[mum].second.first, vec[id].second); } else{ m[mum].second.second = min(m[mum].second.second, vec[id].second); } cur += calc(mum); } else{ ans[id] = base + cur; } } return ans; }
#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...