Submission #914604

#	Time	Username	Problem	Language	Result	Execution time	Memory
914604		nima_aryan	Measures (CEOI22_measures)	C++17	100 / 100	298 ms	20944 KiB

Main

/**
 *    author:  NimaAryan
 *    created: 2024-01-22 14:08:43  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <class Info, class Tag>
class LazySegmentTree {
 public:
  vector<Info> info;
  vector<Tag> tag;
  int n;

  LazySegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
    tag.assign(4 << __lg(n), Tag());
  }

  void pull(int p) {
    info[p] = info[2 * p] + info[2 * p + 1];
  }
  void apply(int p, const Tag& v) {
    info[p].apply(v);
    tag[p].apply(v);
  }
  void push(int p) {
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = Tag();
  }
  void modify(int p, int l, int r, int x, const Info& v) {
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    int m = (l + r) / 2;
    push(p);
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int p, const Info& v) {
    modify(1, 0, n, p, v);
  }

  Info range_query(int p, int l, int r, int lx, int rx) {
    if (l >= rx || r <= lx) {
      return Info();
    }
    if (l >= lx && r <= rx) {
      return info[p];
    }
    int m = (l + r) / 2;
    push(p);
    return range_query(2 * p, l, m, lx, rx) +
           range_query(2 * p + 1, m, r, lx, rx);
  }
  Info range_query(int lx, int rx) {
    return range_query(1, 0, n, lx, rx);
  }
  void range_apply(int p, int l, int r, int lx, int rx,
                  const Tag& v) {
    if (l >= rx || r <= lx) {
      return;
    }
    if (l >= lx && r <= rx) {
      apply(p, v);
      return;
    }
    int m = (l + r) / 2;
    push(p);
    range_apply(2 * p, l, m, lx, rx, v);
    range_apply(2 * p + 1, m, r, lx, rx, v);
    pull(p);
  }
  void range_apply(int lx, int rx, const Tag& v) {
    range_apply(1, 0, n, lx, rx, v);
  }
};

struct Tag {
  i64 add = 0;

  void apply(Tag t) {
    add += t.add;
  }
};

constexpr i64 inf = 1E16;
struct Info {
  i64 min_value = +inf, max_value = -inf;

  void apply(Tag t) {
    if (min_value != +inf) {
      min_value += t.add;
    }
    if (max_value != -inf) {
      max_value += t.add;
    }
  }
};
Info operator+(Info a, Info b) {
  return {min(a.min_value, b.min_value), max(a.max_value, b.max_value)};
}

template <typename T>
class Fenwick {
 public:
  int n;
  vector<T> a;

  Fenwick(int n) : n(n) {
    a.assign(n, T{});
  }

  void add(int x, T v) {
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1] += v;
    }
  }
  T sum(int x) {
    T res{};
    for (int i = x; i > 0; i -= i & -i) {
      res += a[i - 1];
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, m, D;
  cin >> n >> m >> D;

  vector<int> a(n + m);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = n; i < n + m; ++i) {
    cin >> a[i];
  }

  vector<int> p(n + m);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  vector<int> order(n + m);
  for (int i = 0; i < n + m; ++i) {
    order[p[i]] = i;
  }

  i64 t = 0;
  LazySegmentTree<Info, Tag> seg(n + m);
  Fenwick<int> fen(n + m);
  auto add = [&](int x) {
    i64 val = a[x] - 1LL * fen.sum(order[x]) * D;
    seg.range_apply(order[x] + 1, n + m, {-D});
    i64 left = seg.range_query(0, order[x]).max_value;
    i64 right = seg.range_query(order[x] + 1, n + m).min_value;
    t = max({t, left - val, val - right, left - right});
    seg.modify(order[x], {val, val});
    fen.add(order[x], +1);
  };
  for (int i = 0; i < n; ++i) {
    add(i);
  }
  for (int i = n; i < n + m; ++i) {
    add(i);
    if (t % 2 == 0) {
      cout << t / 2 << " \n"[i + 1 == n + m];
    } else {
      cout << t / 2 << ".5" << " \n"[i + 1 == n + m];
    }
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41