제출 #800489

#제출 시각아이디문제언어결과실행 시간메모리
800489WLZMeasures (CEOI22_measures)C++17
0 / 100
260 ms59228 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "templates/debug.h" #else #define debug(...) 0 #endif #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define eb emplace_back #define pb push_back #define MP make_pair #define MT make_tuple #define all(x) (x).begin(), (x).end() #define SZ(x) (int) x.size() using ll = long long; using ull = unsigned ll; using lll = __int128_t; using ulll = __uint128_t; using ld = long double; using ii = pair<int, int>; using vi = vector<int>; using vll = vector<ll>; using vii = vector<ii>; template<typename T> using max_pq = priority_queue<T>; template<typename T> using min_pq = priority_queue<T, vector<T>, greater<T>>; template<typename T> void cmax(T &a, const T &b) { a = max(a, b); } template<typename T> void cmin(T &a, const T &b) { a = min(a, b); } const int INF = 0x3f3f3f3f; const ll LINF = (ll) 1e18; const double DINF = 1.0 / 0.0; const double pi = acos(-1); const double EPS = 1e-9; void solve(int current_case); int main() { ios::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; for (int q = 1; q <= t; q++) solve(q); return 0; } struct node { int l, r; ll mn, mx, sum, lazy; node *left ,*right; }; node *build(int l, int r) { if (l == r) return new node{l, r, LINF, -LINF, 0, 0, nullptr, nullptr}; node *left = build(l, (l + r) / 2), *right = build((l + r) / 2 + 1, r); return new node{l, r, LINF, -LINF, 0, 0, left, right}; } void propagate(node *cur) { if (cur->lazy == 0) return; cur->mn += cur->lazy; cur->mx += cur->lazy; cur->sum += cur->lazy * (cur->r - cur->l + 1); if (cur->left != nullptr) { cur->left->lazy += cur->lazy; cur->right->lazy += cur->lazy; } cur->lazy = 0; } pair<ll, ll> query(node *cur, int l, int r) { // min, max propagate(cur); if (l > cur->r || r < cur->l) return MP(LINF, -LINF); if (l <= cur->l && cur->r <= r) return MP(cur->mn, cur->mx); pair<ll, ll> lq = query(cur->left, l, r), rq = query(cur->right, l, r); return {min(lq.first, rq.first), max(lq.second, rq.second)}; } ll query_sum(node *cur, int l, int r) { propagate(cur); if (l > cur->r || r < cur->l) return 0; if (l <= cur->l && cur->r <= r) return cur->sum; return query_sum(cur->left, l, r) + query_sum(cur->right, l, r); } void update(node *cur, int idx, int val) { propagate(cur); if (cur->l == cur->r) { cur->mn = cur->mx = cur->sum = val; return; } if (idx <= cur->left->r) update(cur->left, idx, val); else update(cur->right, idx, val); cur->mx = max(cur->left->mx, cur->right->mx); cur->mn = min(cur->left->mn, cur->right->mn); cur->sum = cur->left->sum + cur->right->sum; } void update(node *cur, int l, int r, ll val) { // add propagate(cur); if (l > cur->r || r < cur->l) return; if (l <= cur->l && cur->r <= r) { cur->lazy += val; propagate(cur); return; } update(cur->left, l, r, val); update(cur->right, l, r, val); cur->mn = min(cur->left->mn, cur->right->mn); cur->mx = max(cur->left->mx, cur->right->mx); cur->sum = cur->left->sum + cur->right->sum; } void solve(int current_case) { int n, m, d; cin >> n >> m >> d; vi a(n), b(m), ord(n + m); vii c; rep(i, 0, n) cin >> a[i], c.eb(a[i], i); rep(i, 0, m) cin >> b[i], c.eb(b[i], i + n); sort(all(c)); rep(i, 0, n + m) ord[c[i].second] = i; vll ans(n + m); node *root = build(0, n + m - 1), *root2 = build(0, n + m - 1); rep(i, 0, n + m) update(root2, i, 0); ll mx = -LINF; rep(i, 0, n + m) { update(root, ord[i], (ll) (i < n ? a[i] : b[i - n]) - query_sum(root2, 0, ord[i] - 1) * d); update(root2, ord[i], 1); update(root, ord[i] + 1, n + m - 1, -d); cmax(mx, query(root, 0, ord[i]).second - query(root, ord[i], n + m - 1).first); ans[i] = mx; } rep(i, n, n + m) { if (ans[i] % 2 == 0) cout << ans[i] / 2 << " "; else cout << ans[i] / 2 << ".5 "; } cout << '\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...