oj.uz

Submission #800529

# Submission time Handle Problem Language Result Execution time Memory
800529 2023-08-01T15:54:21 Z WLZ Measures (CEOI22_measures) C++17
100 / 100
 654 ms 75864 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "templates/debug.h"
#else
#define debug(...) 0
#endif

#define int long long

#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);

signed 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 > idx || cur->r < idx) return;
  if (cur->l == cur->r) {
    cur->mn = cur->mx = cur->sum = val;
    return;
  }
  update(cur->left, idx, val);
  update(cur->right, idx, 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 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';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 2 ms 980 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 3 ms 980 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 602 ms 72588 KB Output is correct
10 Correct 578 ms 72584 KB Output is correct
11 Correct 261 ms 72724 KB Output is correct
12 Correct 308 ms 72608 KB Output is correct
13 Correct 299 ms 72252 KB Output is correct
14 Correct 271 ms 72564 KB Output is correct
15 Correct 621 ms 72000 KB Output is correct
16 Correct 259 ms 72664 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 71796 KB Output is correct
2 Correct 277 ms 73692 KB Output is correct
3 Correct 282 ms 75604 KB Output is correct
4 Correct 272 ms 73408 KB Output is correct
5 Correct 276 ms 74776 KB Output is correct
6 Correct 269 ms 73776 KB Output is correct
7 Correct 279 ms 74724 KB Output is correct
8 Correct 291 ms 73580 KB Output is correct
9 Correct 271 ms 73348 KB Output is correct
10 Correct 287 ms 75832 KB Output is correct
11 Correct 270 ms 74220 KB Output is correct
12 Correct 287 ms 75272 KB Output is correct
13 Correct 295 ms 73492 KB Output is correct
14 Correct 277 ms 75584 KB Output is correct
15 Correct 276 ms 75156 KB Output is correct
16 Correct 275 ms 73060 KB Output is correct
17 Correct 280 ms 74804 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 71796 KB Output is correct
2 Correct 277 ms 73692 KB Output is correct
3 Correct 282 ms 75604 KB Output is correct
4 Correct 272 ms 73408 KB Output is correct
5 Correct 276 ms 74776 KB Output is correct
6 Correct 269 ms 73776 KB Output is correct
7 Correct 279 ms 74724 KB Output is correct
8 Correct 291 ms 73580 KB Output is correct
9 Correct 271 ms 73348 KB Output is correct
10 Correct 287 ms 75832 KB Output is correct
11 Correct 270 ms 74220 KB Output is correct
12 Correct 287 ms 75272 KB Output is correct
13 Correct 295 ms 73492 KB Output is correct
14 Correct 277 ms 75584 KB Output is correct
15 Correct 276 ms 75156 KB Output is correct
16 Correct 275 ms 73060 KB Output is correct
17 Correct 280 ms 74804 KB Output is correct
18 Correct 609 ms 73876 KB Output is correct
19 Correct 624 ms 75540 KB Output is correct
20 Correct 280 ms 75552 KB Output is correct
21 Correct 320 ms 73532 KB Output is correct
22 Correct 450 ms 73860 KB Output is correct
23 Correct 298 ms 73784 KB Output is correct
24 Correct 654 ms 74232 KB Output is correct
25 Correct 280 ms 73372 KB Output is correct
26 Correct 606 ms 73344 KB Output is correct
27 Correct 607 ms 75864 KB Output is correct
28 Correct 526 ms 73788 KB Output is correct
29 Correct 593 ms 75144 KB Output is correct
30 Correct 321 ms 73352 KB Output is correct
31 Correct 322 ms 75408 KB Output is correct
32 Correct 294 ms 75160 KB Output is correct
33 Correct 632 ms 73060 KB Output is correct
34 Correct 347 ms 74756 KB Output is correct