Submission #1091912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091912		vjudge1	Measures (CEOI22_measures)	C++14	24 / 100	274 ms	22100 KiB

Main

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41