oj.uz

Submission #1091912

# Submission time Handle Problem Language Result Execution time Memory
1091912 2024-09-22T14:25:55 Z vjudge1 Measures (CEOI22_measures) C++14
24 / 100
 274 ms 22100 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int OFF = 1 << 18;
const LL INF = 1e18;
struct SegTree {
  LL minv[2 * OFF], maxv[2 * OFF], lazy[2 * OFF];
  SegTree() {
    for (int o = 1; o < 2 * OFF; o++) minv[o] = INF, maxv[o] = -INF;
  }
  void push_down(int o) {
    int lc = 2 * o, rc = 2 * o + 1;
    LL &a = lazy[o];
    minv[lc] += a, maxv[lc] += a, lazy[lc] += a;
    minv[rc] += a, maxv[rc] += a, lazy[rc] += a, a = 0;
  }
  void update(int o) {
    int lc = 2 * o, rc = 2 * o + 1;
    minv[o] = min(minv[lc], minv[rc]), maxv[o] = max(maxv[lc], maxv[rc]);
  }
  void set(int p, LL val, int o = 1, int lo = 0, int hi = OFF) {
    if (lo + 1 == hi) {
      minv[o] += val - INF, maxv[o] += val + INF;
      return;
    }
    push_down(o);
    int m = (lo + hi) / 2, lc = 2 * o, rc = 2 * o + 1;
    (p < m) ? set(p, val, lc, lo, m) : set(p, val, rc, m, hi);
    update(o);
  }
  void add(int l, int r, LL val, int o = 1, int lo = 0, int hi = OFF) {
    if (l <= lo && hi <= r) {
      minv[o] += val, maxv[o] += val, lazy[o] += val;
    } else if (r <= lo || hi <= l)
      return;
    else {
      push_down(o);
      int m = (lo + hi) / 2, lc = 2 * o, rc = 2 * o + 1;
      add(l, r, val, lc, lo, m);
      add(l, r, val, rc, m, hi);
      update(o);
    }
  }
  array<LL, 2> query(int l, int r, int i = 1, int lo = 0, int hi = OFF) {
    if (l <= lo && hi <= r) return {minv[i], maxv[i]};
    if (r <= lo || hi <= l) return {INF, -INF};
    push_down(i);
    int mid = (lo + hi) / 2;
    auto p = query(l, r, 2 * i + 0, lo, mid),
         q = query(l, r, 2 * i + 1, mid, hi);
    return {min(p[0], q[0]), max(p[1], q[1])};
  }
} T;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, m;
  LL d;
  cin >> n >> m >> d;
  vector<LL> x(n + m);
  vector<array<LL, 2>> A(n + m);
  for (int i = 0; i < n + m; i++) cin >> x[i], A[i] = {x[i], i};
  sort(A.begin(), A.end());
  vector<int> idx(n + m);
  for (int i = 0; i < n + m; i++) idx[A[i][1]] = i;
  LL sol = 0;
  for (int i = 0; i < n + m; i++) {
    int id = idx[i];
    T.set(id, -x[i]), T.add(id, OFF, d);
    sol = max({sol, T.query(id, OFF)[1] - T.query(0, id)[0],
               T.query(id + 1, OFF)[1] - T.query(0, id + 1)[0]});
    if (i >= n) printf("%lld%s ", sol / 2, (sol % 2 ? ".5" : ""));
  }
  cout << "\n";
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8792 KB Output is correct
2 Correct 7 ms 8796 KB Output is correct
3 Correct 5 ms 8796 KB Output is correct
4 Correct 6 ms 8796 KB Output is correct
5 Correct 6 ms 8796 KB Output is correct
6 Correct 6 ms 8816 KB Output is correct
7 Correct 6 ms 8796 KB Output is correct
8 Correct 6 ms 8716 KB Output is correct
9 Correct 266 ms 19028 KB Output is correct
10 Correct 254 ms 19024 KB Output is correct
11 Correct 194 ms 19284 KB Output is correct
12 Correct 226 ms 19024 KB Output is correct
13 Correct 188 ms 18560 KB Output is correct
14 Correct 221 ms 19024 KB Output is correct
15 Correct 263 ms 18516 KB Output is correct
16 Correct 195 ms 19028 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 20240 KB Output is correct
2 Incorrect 274 ms 22100 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 20240 KB Output is correct
2 Incorrect 274 ms 22100 KB Output isn't correct
3 Halted 0 ms 0 KB -