Submission #1139895

#TimeUsernameProblemLanguageResultExecution timeMemory
1139895repmannNile (IOI24_nile)C++20
0 / 100
33 ms9284 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; int N, M, Q; struct NODE { int parent, ranking; int L, R, minimum, best; ll sum; }DSU[100096]; struct EDGE { int u, v, w; }E[200096]; int C[100096]; inline bool comp(EDGE e1, EDGE e2) {return e1.w < e2.w;} inline ll Get(int i) { if((DSU[i].R - DSU[i].L) & 1) return DSU[i].sum; return DSU[i].sum + DSU[i].minimum; if(((DSU[i].R - DSU[i].L + 1) & 3) == 1) return DSU[i].sum + DSU[i].minimum; return DSU[i].sum + min({DSU[i].best, C[DSU[i].L], C[DSU[i].R]}); } inline int Find(int i) { while(DSU[i].parent != i) i = DSU[i].parent; return i; } inline ll Union(int u, int v) { u = Find(u); v = Find(v); if(u == v) return 0; ll RET = Get(u) + Get(v); if(DSU[u].ranking < DSU[v].ranking) swap(u, v); DSU[u].ranking += DSU[u].ranking == DSU[v].ranking; DSU[v].parent = u; DSU[u].L = min(DSU[v].L, DSU[u].L); DSU[u].R = min(DSU[v].R, DSU[u].R); DSU[u].minimum = min(DSU[v].minimum, DSU[u].minimum); DSU[u].best = min(DSU[v].best, DSU[u].best); DSU[u].sum += DSU[v].sum; RET -= Get(u); return RET; } vector <ll> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> D) { N = W.size(); Q = D.size(); vector <ll> O(Q); vector <pair <int, int>> MO(Q), V(N); for(int i = 0; i < Q; i++) MO[i] = {D[i], i}; sort(MO.begin(), MO.end()); for(int i = 0; i < N; i++) V[i] = {W[i], i}; sort(V.begin(), V.end()); for(int i = 0; i < N; i++) C[V[i].second] = A[V[i].second] - B[V[i].second]; for(int i = 1; i < N; i++) E[++M] = {V[i - 1].second, V[i].second, V[i].first - V[i - 1].first}; for(int i = 2; i < N; i++) E[++M] = {V[i - 1].second, -1, V[i].first - V[i - 2].first}; sort(E + 1, E + M + 1, comp); for(int i = 0; i < N; i++) DSU[V[i].second] = {V[i].second, 0, i, i, A[V[i].second] - B[V[i].second], INT_MAX, B[V[i].second]}; ll temp = 0; for(int i = 0; i < N; i++) temp += A[i]; int i = 1; for(pair <int, int> p : MO) { while((i <= M) && (E[i].w <= p.first)) { if(E[i].v >= 0) temp -= Union(E[i].u, E[i].v); else { E[i].v = Find(E[i].u); temp -= Get(E[i].v); DSU[E[i].v].best = min(A[E[i].u] - B[E[i].u], DSU[E[i].v].best); temp += Get(E[i].v); } i++; } O[p.second] = temp; } return O; }
#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...