Submission #1247260

#TimeUsernameProblemLanguageResultExecution timeMemory
1247260NumberzNile (IOI24_nile)C++20
51 / 100
123 ms24132 KiB
#include "nile.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define vll vector<ll> #define vvll vector<vll> #define pll pair<ll, ll> #define pill pair<ll, pll> #define vpll vector<pll> const ll INF = 1e17; const int MAXN = 1e5+5; const int MAXT = 270000; struct DSU { ll n, totalcost = 0; //id = comp, size = size, evenpot = min cost of element on even position, odd same (where can ) // vll id, size, anyevenopt, anyoddopt, skipeven, skipodd, cost, mn, C; DSU(vll& _C) { n = _C.size(); for (int i = 0; i < n; i++) { C.push_back(_C[i]); id.push_back(i); size.push_back(1); anyevenopt.push_back(i&1 ? INF : _C[i]); anyoddopt.push_back(i&1 ? _C[i] : INF); skipeven.push_back(INF); skipodd.push_back(INF); cost.push_back(_C[i]); totalcost += _C[i]; mn.push_back(i); } } ll find(int x) {return x==id[x] ? x : id[x] = find(id[x]);} void unite_consecutive(int a, int b) { //here we are joining i, i+1 a = find(a); b = find(b); if (size[a] < size[b]) swap(a, b); //if part of same component -> ignore I guess?? if (a==b) return; //now we need to join the information ll newsize = size[a] + size[b]; ll newaeopt = min(anyevenopt[a], anyevenopt[b]), newaopt = min(anyoddopt[a], anyoddopt[b]); ll newskipeven = min(skipeven[a], skipeven[b]), newskipodd = min(skipodd[a], skipodd[b]); ll newmn = min(mn[a], mn[b]); ll newcost = INF; if (newsize&1) { //skip any same parity (even, skip, even) or skip skip other parity (odd, skip, odd) with (_,_) if (newmn&1) newcost = min({newcost, newaopt, newskipeven}); else newcost = min({newcost, newaeopt, newskipodd}); } else newcost = 0; //now join all info together totalcost = totalcost - cost[a] - cost[b] + newcost; id[b] = a; size[a] = newsize; anyevenopt[a] = newaeopt; anyoddopt[a] = newaopt; skipeven[a] = newskipeven; skipodd[a] = newskipodd; cost[a] = newcost; mn[a] = newmn; } void unite_skip(int i) { //i will be in a specific component a int a = find(i); //we just have to update the skip vals if (i&1) { //we update odd skip (i is already included in anyskip) skipodd[a] = min(skipodd[a], C[i]); } else skipeven[a] = min(skipeven[a], C[i]); if (size[a]&1) { //update the cost if ((i-mn[a])%2) { ll newcost = (i&1 ? min(cost[a], skipodd[a]) : min(cost[a], skipeven[a])); totalcost = totalcost - cost[a] + newcost; cost[a] = newcost; } } } }; vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) { int n = A.size(), q = E.size(); vll C(n, 0), res(q, 0); ll basecost = accumulate(B.begin(), B.end(), 0LL); for (int i = 0; i < n; i++) C[i] = A[i] - B[i]; priority_queue<pill, vector<pill>, greater<pill>> events; //here all indicies are sorted by Weight vll indices(n); iota(indices.begin(), indices.end(), 0); sort(indices.begin(), indices.end(), [&](int i, int j) {return W[i] < W[j];}); for (int i = 0; i < n-1; i++) events.push({abs(W[indices[i]] - W[indices[i+1]]), {0, i}}); for (int i = 1; i < n-1; i++) events.push({abs(W[indices[i+1]] - W[indices[i-1]]), {1, i}}); for (int i = 0; i < q; i++) events.push({E[i], {2, i}}); vll _C; for (int i : indices) _C.push_back(C[i]); DSU uf(_C); while (!events.empty()) { auto p = events.top(); events.pop(); if (p.second.first==2) { //process query; res[p.second.second] = uf.totalcost+basecost; } else if (p.second.first==0) { //joining two consecutive things int a = indices[p.second.second], b = indices[p.second.second+1]; uf.unite_consecutive(a, b); } else { //joining 2 seperate int i = indices[p.second.second]; uf.unite_skip(i); } } //for (int i : res) cout << i << ' '; return res; }
#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...