Submission #1247934

#TimeUsernameProblemLanguageResultExecution timeMemory
1247934clementineNile (IOI24_nile)C++20
51 / 100
71 ms12220 KiB
#include "nile.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; #pragma region Debugger // Base printer for general types template<typename T> void __print(const T& x) { cerr << x; } // Specialized printer for string void __print(const string& x) { cerr << '"' << x << '"'; } void __print(const char* x) { cerr << '"' << x << '"'; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(bool x) { cerr << (x ? "true" : "false"); } // Specialized printer for pair template<typename T1, typename T2> void __print(const pair<T1, T2>& p) { cerr << "("; __print(p.first); cerr << ", "; __print(p.second); cerr << ")"; } // For containers: vector, set, map, etc. (but not string or pair) template<typename T, typename = void> struct is_container : false_type {}; template<typename T> struct is_container<T, std::void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {}; template<typename T> typename enable_if<is_container<T>::value && !is_same<T, string>::value, void>::type __print(const T& container) { cerr << "{"; bool first = true; for (const auto& item : container) { if (!first) cerr << ", "; __print(item); first = false; } cerr << "}"; } // Recursive variadic template debug printer template<typename T> void _debug_cerr(const char* name, T&& value) { cerr << name << ": "; __print(value); cerr << '\n'; } template<typename T, typename... Args> void _debug_cerr(const char* names, T&& value, Args&&... args) { const char* comma = strchr(names, ','); cerr.write(names, comma - names) << ": "; __print(value); cerr << ", "; _debug_cerr(comma + 1, forward<Args>(args)...); } // Macro interface #define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__) #pragma endregion vector<pair<int ,int>> w; // first int is size, second is the index it is // dsu node struct Node { int l, r; // r is the parent int size; int min_even, min_odd; int min_safe_even, min_safe_odd; Node(int l, int r, int size, ll e, ll o, ll se, ll so) : l(l), r(r), size(size), min_even(e), min_odd(o), min_safe_even(se), min_safe_odd(so) {} }; vector<Node> dsu_arr; int find(int a) { if(dsu_arr[a].r == a)return a; dsu_arr[a].r = find(dsu_arr[a].r); return dsu_arr[a].r; } vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) { int Q = (int)E.size(); vector<ll> R(Q, 0); ll total_cost = 0; int n = (int) W.size(); vector<pair<int, int>> e; // first is D[i], second is index vector<pair<int, int>> safe_dist(n, {-1, 0}); vector<pair<int, int>> consec_dist(n - 1, {-1, 0}); // second is the index to the left ie dist i i+1 vector<int> diff(n, 0); for(int i = 0; i < n; i ++) { total_cost += A[i]; w.push_back({W[i], i}); } sort(w.begin(), w.end()); for(int i = 0; i < n; i ++) { diff[w[i].second] = A[i] - B[i]; } for(int i = 0 ; i< Q; i ++) { e.push_back({E[i], i}); } sort(e.begin(), e.end()); for(int i = 1; i < n-1; i ++) { safe_dist[i] = {w[i+1].first - w[i-1].first, i}; } sort(safe_dist.begin(), safe_dist.end()); int safe_dist_idx = 2; for(int i = 0; i < n-1; i ++) { consec_dist[i] = {w[i+1].first - w[i].first, i}; } sort(consec_dist.begin(), consec_dist.end()); int consec_dist_idx = 0; // initualize dsu for(int i = 0; i < n; i ++) { dsu_arr.push_back(Node(i, i, 1, diff[i], INT32_MAX, INT32_MAX, INT32_MAX)); } //debug(total_cost); for(auto eval: e) { //debug(eval); // for each consecutive thing that is newly joined while(consec_dist_idx < consec_dist.size() && consec_dist[consec_dist_idx].first <= eval.first) { int current_idx = consec_dist[consec_dist_idx].second; int parent = find(current_idx + 1); //debug(current_idx, parent); // update child stat to point to parent dsu_arr[current_idx].r = parent; // update the parent's stats // what happens to the mins? if(dsu_arr[current_idx].size % 2 == 1) { total_cost -= min(dsu_arr[current_idx].min_even, dsu_arr[current_idx].min_safe_odd); } if(dsu_arr[parent].size % 2 == 1) { total_cost -= min(dsu_arr[parent].min_even, dsu_arr[parent].min_safe_odd); //debug(dsu_arr[parent].min_even, dsu_arr[parent].min_safe_odd); } //debug(total_cost); if(dsu_arr[current_idx].size % 2 == 0) { //debug(dsu_arr[current_idx].size % 2); int new_min_even = min(dsu_arr[parent].min_even, dsu_arr[current_idx].min_even); int new_min_odd = min(dsu_arr[parent].min_odd, dsu_arr[current_idx].min_odd); int new_min_safe_even = min(dsu_arr[parent].min_safe_even, dsu_arr[current_idx].min_safe_even); int new_min_safe_odd = min(dsu_arr[parent].min_safe_odd, dsu_arr[current_idx].min_safe_odd); dsu_arr[parent].min_even = new_min_even; dsu_arr[parent].min_odd = new_min_odd; dsu_arr[parent].min_safe_even = new_min_safe_even; dsu_arr[parent].min_safe_odd = new_min_safe_odd; } else { //debug(dsu_arr[parent].min_safe_odd, dsu_arr[current_idx].min_even); int new_min_even = min(dsu_arr[parent].min_odd, dsu_arr[current_idx].min_even); int new_min_odd = min(dsu_arr[parent].min_even, dsu_arr[current_idx].min_odd); int new_min_safe_even = min(dsu_arr[parent].min_safe_odd, dsu_arr[current_idx].min_safe_even); int new_min_safe_odd = min(dsu_arr[parent].min_safe_even, dsu_arr[current_idx].min_safe_odd); dsu_arr[parent].min_even = new_min_even; dsu_arr[parent].min_odd = new_min_odd; dsu_arr[parent].min_safe_even = new_min_safe_even; dsu_arr[parent].min_safe_odd = new_min_safe_odd; } dsu_arr[parent].size += dsu_arr[current_idx].size; // updating paret size only now to not have problems if(dsu_arr[parent].size % 2 == 1) { total_cost += min(dsu_arr[parent].min_safe_odd, dsu_arr[parent].min_even); } //debug(dsu_arr[parent].min_even, dsu_arr[parent].min_safe_odd, total_cost); consec_dist_idx ++; } // update safe distances while(safe_dist_idx < safe_dist.size() && safe_dist[safe_dist_idx].first <= eval.first) { int current_idx = safe_dist[safe_dist_idx].second; int parent = find(current_idx); //debug(safe_dist[safe_dist_idx].first, current_idx, parent); if(dsu_arr[parent].size % 2 == 1 && (parent - current_idx) % 2 == 1) //if the current idx is on an odd spot then min odd must be updated to min(previous min, current idx difference) { //debug(dsu_arr[parent].size); if(dsu_arr[parent].min_safe_odd <= dsu_arr[parent].min_even) { total_cost -= dsu_arr[parent].min_safe_odd; total_cost += min(dsu_arr[parent].min_safe_odd, diff[current_idx]); } else { total_cost -= dsu_arr[parent].min_even; total_cost += min(dsu_arr[parent].min_even, diff[current_idx]); } dsu_arr[parent].min_safe_odd = min(dsu_arr[parent].min_safe_odd, diff[current_idx]); } else if( dsu_arr[parent].size % 2 == 0 && (parent - current_idx) % 2 == 0) { dsu_arr[parent].min_safe_odd = min(dsu_arr[parent].min_safe_odd, diff[current_idx]); } safe_dist_idx ++; } R[eval.second] = total_cost; } 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...