oj.uz

Submission #800526

# Submission time Handle Problem Language Result Execution time Memory
800526 2023-08-01T15:50:25 Z WLZ Measures (CEOI22_measures) C++17
0 / 100
 303 ms 59224 KB 
#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 > 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Incorrect 2 ms 852 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 3 ms 840 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 3 ms 852 KB Output is correct
8 Incorrect 2 ms 852 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 58072 KB Output is correct
2 Incorrect 303 ms 59224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 58072 KB Output is correct
2 Incorrect 303 ms 59224 KB Output isn't correct
3 Halted 0 ms 0 KB -