Submission #1082894

#TimeUsernameProblemLanguageResultExecution timeMemory
1082894_callmelucianMeasures (CEOI22_measures)C++14
59 / 100
1573 ms35032 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) struct IT { vector<ll> hi, lo, lazy; IT (int sz) : hi(4 * sz), lo(4 * sz), lazy(4 * sz) {} ll addLo (ll a, ll b) { return (min(a, b) == LLONG_MIN || max(a, b) == LLONG_MAX ? LLONG_MAX : a + b); } ll addHi (ll a, ll b) { return (min(a, b) == LLONG_MIN || max(a, b) == LLONG_MAX ? LLONG_MIN : a + b); } ll getHi (int k) { return addHi(hi[k], lazy[k]); } ll getLo (int k) { return addLo(lo[k], lazy[k]); } void refine (int k) { hi[k] = max(getHi(2 * k), getHi(2 * k + 1)); lo[k] = min(getLo(2 * k), getLo(2 * k + 1)); } void pushDown (int k) { lazy[2 * k] = addHi(lazy[2 * k], lazy[k]), lazy[2 * k + 1] = addHi(lazy[2 * k + 1], lazy[k]); lazy[k] = 0, refine(k); } void update (int a, int b, ll incr, int k, int l, int r) { if (b < l || r < a) return; if (a <= l && r <= b) { lazy[k] = addHi(lazy[k], incr); return; } pushDown(k); int mid = (l + r) >> 1; update(a, b, incr, 2 * k, l, mid); update(a, b, incr, 2 * k + 1, mid + 1, r); refine(k); } ll query (int a, int b, int k, int l, int r) { if (b < l || r < a) return LLONG_MIN; if (a <= l && r <= b) return getHi(k); pushDown(k); int mid = (l + r) >> 1; return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r)); } int walk (ll targ, int k, int l, int r) { if (l == r) return l; pushDown(k); int mid = (l + r) >> 1; if (getLo(2 * k) < targ) return walk(targ, 2 * k, l, mid); return walk(targ, 2 * k + 1, mid + 1, r); } int findID (int a, int b, ll targ, int k, int l, int r) { if (b < l || r < a) return INT_MAX; if (a <= l && r <= b) return (getLo(k) < targ ? walk(targ, k, l, r) : INT_MAX); pushDown(k); int mid = (l + r) >> 1; int cur = findID(a, b, targ, 2 * k, l, mid); return (cur < INT_MAX ? cur : findID(a, b, targ, 2 * k + 1, mid + 1, r)); } ll access (int pos, int k, int l, int r) { if (l == r) return getLo(k); int mid = (l + r) >> 1; if (pos <= mid) return addLo(lazy[k], access(pos, 2 * k, l, mid)); return addLo(lazy[k], access(pos, 2 * k + 1, mid + 1, r)); } void build (vector<ll> &a, int k, int l, int r) { if (l == r) { hi[k] = lo[k] = a[l]; return; } int mid = (l + r) >> 1; build(a, 2 * k, l, mid); build(a, 2 * k + 1, mid + 1, r); refine(k); } }; const int mn = 2e5 + 50; int st[mn], nxt[mn], prv[mn]; bool ok (vector<pl> vec, ll D, ll mov) { ll last = LLONG_MIN; for (pl it : vec) { ll init = it.first, cur = max(init - mov, last + D); if (cur > init + mov) return 0; last = cur; } return 1; } ll solve (vector<pl> vec, ll D) { if (ok(vec, D, 0)) return 0; ll ans = 0; for (ll msk = (1LL << 60); msk > 0; msk >>= 1) if (!ok(vec, D, ans | msk)) ans |= msk; return ans + 1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, D; cin >> n >> m >> D; D *= 2; vector<pl> vec(n + m); for (int i = 0; i < n + m; i++) { cin >> st[i]; st[i] *= 2; vec[i] = {st[i], i}, nxt[i] = i + 1, prv[i] = i - 1; } prv[n + m] = n + m - 1; sort(all(vec)); ll curAns = solve(vec, D), last = LLONG_MIN; function<int(int)> getID = [&] (int initID) { return lower_bound(all(vec), make_pair((ll)st[initID], (ll)initID)) - vec.begin(); }; vector<ll> a(n + m); for (int i = 0; i < n + m; i++) { ll init = vec[i].first, cur = max(init - curAns, last + D); a[i] = cur - init, last = cur; } IT tree(n + m); tree.build(a, 1, 0, n + m - 1); vector<ll> ans; for (int i = n + m - 1; i >= n; i--) { ans.push_back(curAns); int cur = getID(i); tree.update(cur, cur, LLONG_MIN, 1, 0, n + m - 1); if (prv[cur] >= 0) nxt[prv[cur]] = nxt[cur]; prv[nxt[cur]] = prv[cur]; if (nxt[cur] < n + m) { int tmp = nxt[cur]; while (tmp < n + m) { ll goCur = tree.access(tmp, 1, 0, n + m - 1), pos = vec[tmp].first + goCur; ll gap = goCur + curAns; if (prv[tmp] >= 0) { ll posL = vec[prv[tmp]].first + tree.access(prv[tmp], 1, 0, n + m - 1); gap = min(gap, pos - posL - D); } if (!gap) break; int bound = prv[min(n + m, tree.findID(tmp, n + m - 1, goCur, 1, 0, n + m - 1))]; tree.update(tmp, bound, -gap, 1, 0, n + m - 1); tmp = nxt[bound]; } } ll decrAns = min(curAns, (curAns - tree.getHi(1)) / 2LL); tree.update(0, n + m - 1, decrAns, 1, 0, n + m - 1); curAns -= decrAns; } reverse(all(ans)); for (ll u : ans) cout << u / 2 << (u % 2 ? ".5 " : " "); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...