Submission #1208940

#TimeUsernameProblemLanguageResultExecution timeMemory
1208940vaneaNile (IOI24_nile)C++20
45 / 100
81 ms17068 KiB
#include "nile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 1e5+10; const ll INF = 1e18; ll p[mxN], mn_odd[mxN], mn_even[mxN], mn_idx[mxN], mn_add[mxN], c[mxN]; ll ans = 0; int get(int x) { return p[x] < 0 ? x : p[x] = get(p[x]); } void uni(int a, int b) { int a1 = a, b1 = b; a = get(a); b = get(b); if(a == b) { if(b1-a1 == 2) { ll now = c[a1+1]; if(now < mn_add[a]) { if(-p[a] & 1) { ll mn = mn_add[a]; if(mn_idx[a] & 1) { mn = min(mn, mn_odd[a]); } else { mn = min(mn, mn_even[a]); } ans -= mn; mn_add[a] = now; mn = mn_add[a]; if(mn_idx[a] & 1) { mn = min(mn, mn_odd[a]); } else { mn = min(mn, mn_even[a]); } ans += mn; } mn_add[a] = now; } } return ; } if(-p[a] & 1) { ll mn = mn_add[a]; if(mn_idx[a] & 1) { mn = min(mn, mn_odd[a]); } else { mn = min(mn, mn_even[a]); } ans -= mn; } if(-p[b] & 1) { ll mn = mn_add[b]; if(mn_idx[b] & 1) { mn = min(mn, mn_odd[b]); } else { mn = min(mn, mn_even[b]); } ans -= mn; } p[a] += p[b]; p[b] = a; mn_idx[a] = min(mn_idx[a], mn_idx[b]); mn_odd[a] = min(mn_odd[a], mn_odd[b]); mn_even[a] = min(mn_even[a], mn_even[b]); mn_add[a] = min(mn_add[a], mn_add[b]); if(-p[a] & 1) { ll mn = mn_add[a]; if(mn_idx[a] & 1) { mn = min(mn, mn_odd[a]); } else { mn = min(mn, mn_even[a]); } ans += mn; } } vector<ll> calculate_costs(vector<int> w, vector<int> a, vector<int> b, vector<int> e) { int n = w.size(), q = e.size(); vector<array<ll, 3>> v(n); for(int i = 0; i < n; i++) { v[i][0] = w[i]; } for(int i = 0; i < n; i++) { v[i][1] = a[i]; } for(int i = 0; i < n; i++) { v[i][2] = b[i]; ans += b[i]; } sort(v.begin(), v.end()); for(int i = 0; i < n; i++) { p[i] = -1; mn_add[i] = INF; mn_odd[i] = INF; mn_even[i] = INF; mn_idx[i] = i; c[i] = v[i][1]-v[i][2]; if(i & 1) mn_odd[i] = c[i]; else mn_even[i] = c[i]; ans += c[i]; } vector<array<ll, 3>> pairs; for(int i = 0; i < n-1; i++) { pairs.push_back({v[i+1][0]-v[i][0], i, i+1}); if(i+2 < n) pairs.push_back({v[i+2][0]-v[i][0], i, i+2}); } sort(pairs.begin(), pairs.end()); int last = 0; vector<array<int, 2>> queries; for(int i = 0; i < q; i++) { queries.push_back({e[i], i}); } sort(queries.begin(), queries.end()); vector<ll> res(q); for(int i = 0; i < q; i++) { while(last < pairs.size() && pairs[last][0] <= queries[i][0]) { uni(pairs[last][1], pairs[last][2]); ++last; } res[queries[i][1]] = ans; } return res; } /*int main() { //ios_base::sync_with_stdio(0); //cin.tie(0); vector<int> w = {15, 12, 2, 10, 21}; vector<int> a = {5, 4, 5, 6, 3}; vector<int> b = {1, 2, 2, 3, 2}; vector<int> e = {5, 9, 1}; vector<ll> real_ans = calculate_costs(w, a, b, e); for(auto it : real_ans) { cout << it << '\n'; } }*/
#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...