Submission #1211404

#TimeUsernameProblemLanguageResultExecution timeMemory
1211404sula2Nile (IOI24_nile)C++20
38 / 100
107 ms13420 KiB
#include <bits/stdc++.h> #define all(a) a.begin(), a.end() #define popcount(x) __builtin_popcountll(x) using namespace std; using namespace chrono; struct DSU { vector<long long> par, size, mn_odd, mn_even, ans, costs; long long sum = 0; DSU(long long n, vector<long long> C) : par(n), size(n, 1), mn_odd(C), ans(C), costs(C) { mn_even.assign(n, INT_MAX); sum = accumulate(all(C), 0LL); iota(all(par), 0); } long long find(long long u) { return par[u] == u ? u : par[u] = find(par[u]); } void add(long long u) { u = find(u); if (size[u] & 1) sum += ans[u]; } void subtract(long long u) { u = find(u); if (size[u] & 1) sum -= ans[u]; } void merge(long long u, long long v) { if (v-u == 1) { u = find(u), v = find(v); subtract(u); subtract(v); if (size[u] & 1) { swap(mn_odd[v], mn_even[v]); } mn_odd[u] = min(mn_odd[u], mn_odd[v]); mn_even[u] = min(mn_even[u], mn_even[v]); ans[u] = min(ans[u], mn_odd[u]); ans[u] = min(ans[u], ans[v]); par[v] = u; size[u] += size[v]; add(u); } else { long long r = find(u); subtract(r); ans[r] = min(ans[r], costs[u+1]); add(r); } } }; vector<long long> calculate_costs( vector<int> W, vector<int> A, vector<int> B, vector<int> E ) { int n = W.size(), q = E.size(); vector<int> ind_W(n); iota(all(ind_W), 0); sort(all(ind_W), [&](int i, int j) { return W[i] < W[j]; }); vector<int> new_W(n); vector<long long> C(n); for (int i = 0; i < n; i++) { new_W[i] = W[ind_W[i]]; C[i] = A[ind_W[i]] - B[ind_W[i]]; } swap(new_W, W); vector<int> ind_E(q); iota(all(ind_E), 0); sort(all(ind_E), [&](int i, int j) { return E[i] < E[j]; }); vector<array<int, 3>> edges; for (int i = 0; i < n-1; i++) { assert(W[i] <= W[i+1]); edges.push_back({W[i+1] - W[i], i, i+1}); if (i+2 < n) edges.push_back({W[i+2] - W[i], i, i+2}); } sort(all(edges)); DSU D(n, C); int ptr = 0; long long sum_B = accumulate(all(B), 0LL); vector<long long> ans(q); for (int i : ind_E) { while (ptr < edges.size() && edges[ptr][0] <= E[i]) { int u = edges[ptr][1]; int v = edges[ptr][2]; D.merge(u, v); ptr++; } ans[i] = D.sum + sum_B; } 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...