Submission #1190209

#TimeUsernameProblemLanguageResultExecution timeMemory
1190209theyeia나일강 (IOI24_nile)C++20
100 / 100
149 ms21696 KiB
#include "nile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<ll,ll>; using vi = vector<int>; using vl = vector<ll>; using tl = tuple<ll,ll,ll>; const ll INF = 1e9 + 7; #define F first #define S second #define sor(x) sort(begin(x), end(x)) #define FOR(i, a, b) for (int i = a; i < b; i++) // Variables int n, q, p = 2; ll ans = 0; tl id = {INF, INF, INF}; vector<pl> Art, Queries, Dif, Dif2; vector<tl> Sg; vi Link, Left, Right; vl Ans, SavedCosts; // Combine function tl f(tl x, tl y) { return {min(get<0>(x), get<0>(y)), min(get<1>(x), get<1>(y)), min(get<2>(x), get<2>(y))}; } // Builds segment tree and union find void build() { // Segment tree while (p < n) p *= 2; Sg.resize(2 * p, id); Sg[0] = {0, 0, 0}; for (int i = p; i < 2 * p; i++) { ll val0 = (i % 2) ? INF : Art[i - p].S; ll val1 = (i % 2) ? Art[i - p].S : INF; Sg[i] = {val0, val1, INF}; } for (int i = p - 1; i > 0; i--) { Sg[i] = f(Sg[2 * i], Sg[2 * i + 1]); } // Union-find Link.resize(n, 0); Left.resize(n, 0); Right.resize(n, 0); SavedCosts.resize(n, 0); FOR(i, 0, n) { Link[i] = i; Left[i] = i; Right[i] = i; SavedCosts[i] = Art[i].S; } Ans.resize(q, 0); } // Point updates void update(int index, ll value, int lo, int hi, int node) { if (hi < index || index < lo) return; if (lo == hi) { Sg[node] = {get<0>(Sg[node]), get<1>(Sg[node]), value}; return; } int mid = (lo + hi) / 2; update(index, value, lo, mid, 2 * node); update(index, value, mid + 1, hi, 2 * node + 1); Sg[node] = f(Sg[2 * node], Sg[2 * node + 1]); } // Range minimum query ll query(int l, int r, int lo, int hi, int node, int mode) { if (hi < l || r < lo) return INF; if (l <= lo && hi <= r) { if (mode == 0) return get<0>(Sg[node]); if (mode == 1) return get<1>(Sg[node]); if (mode == 2) return get<2>(Sg[node]); } int mid = (lo + hi) / 2; return min(query(l, r, lo, mid, 2 * node, mode), query(l, r, mid + 1, hi, 2 * node + 1, mode)); } // Returns cost to process range (ONLY CALL ON REPRESENTATIVES) ll cost(int u) { if ((Right[u] - Left[u]) % 2) return 0; ll a = query(Left[u], Right[u], 0, p - 1, 1, 2); ll b = query(Left[u], Right[u], 0, p - 1, 1, Left[u] % 2); return min(a, b); } // Find function with path compression int find(int u) { return (u == Link[u]) ? u : Link[u] = find(Link[u]); } void unite(int u, int v) { ans -= SavedCosts[u] + SavedCosts[v]; if (Left[v] - Left[v] > Right[u] - Left[u]) swap(u, v); Link[v] = u; Left[u] = min(Left[u], Left[v]); Right[u] = max(Right[u], Right[v]); SavedCosts[u] = cost(u); ans += SavedCosts[u]; } // Reads input void read(vi W, vi A, vi B, vi E) { n = W.size(); q = E.size(); Art.resize(n, {2 * INF, INF}); FOR(i, 0, n) { ll w = (ll)W[i], a = (ll)A[i], b = (ll)B[i]; Art.push_back({w, a - b}); ans += a; } sor(Art); FOR(i, 0, n - 1) { Dif.push_back({Art[i + 1].F - Art[i].F, i}); if (0 < i) Dif2.push_back({Art[i + 1].F - Art[i - 1].F, i}); } sor(Dif); sor(Dif2); FOR(i, 0, q) { ll e = (ll)E[i]; Queries.push_back({e, i}); } sor(Queries); } // Main function vl calculate_costs(vi W, vi A, vi B, vi E) { read(W, A, B, E); build(); //for (auto a : Art) cout << "(" << a.F << "," << a.S << ") "; cout << endl; //for (auto s : Sg) cout << "(" << get<0>(s) << "," << get<1>(s) << "," << get<2>(s) << ") "; cout << endl; //cout << query(0, 0, 0, p - 1, 1, 0) << " " << query(0, 0, 0, p - 1, 1, 1) << " " << query(0, 0, 0, p - 1, 1, 2) << endl; int r1 = 0, r2 = 0; FOR(i, 0, q) { ll d = Queries[i].F; while (r2 < n - 2 && Dif2[r2].F <= d) { int u = Dif2[r2].S; update(u, Art[u].S, 0, p - 1, 1); r2++; u = find(u); ans -= SavedCosts[u]; SavedCosts[u] = cost(u); ans += SavedCosts[u]; } while (r1 < n - 1 && Dif[r1].F <= d) { int u = Dif[r1].S; unite(find(u), find(u + 1)); r1++; } //FOR(s, 0, n) cout << find(s) << " "; cout << endl; //FOR(s, 0, n) cout << "(" << Left[s] << "," << Right[s] << ") "; cout << endl; //FOR(s, 0, n) cout << cost(find(s)) << " "; cout << endl; //cout << r1 << " " << r2 << endl; //for (auto s : Sg) cout << "(" << get<0>(s) << "," << get<1>(s) << "," << get<2>(s) << ") "; cout << endl; //cout << endl; Ans[Queries[i].S] = ans; } 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...