Submission #1201622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201622		zfs732	New Home (APIO18_new_home)	C++20	100 / 100	1598 ms	122188 KiB

new_home

/*
 * _|_|_|_|_|  _|_|_|_|    _|_|_|  _|_|_|_|_|  _|_|_|      _|_|
 *       _|    _|        _|                _|        _|  _|    _|
 *     _|      _|_|_|      _|_|          _|      _|_|        _|
 *   _|        _|              _|      _|            _|    _|
 * _|_|_|_|_|  _|        _|_|_|      _|        _|_|_|    _|_|_|_|
 */

#include <bits/stdc++.h>

constexpr int maxN = 3E5 + 2;
constexpr int INF = 1E8;

int N, M, K, Q, ans[maxN];
std::vector<std::tuple<int, int, int, int>> events;
std::vector<int> disc;

namespace SegmentTree {
  std::multiset<int> st[maxN];
  int tree[maxN << 2];

#define T(u) tree[u]
#define LS(u) (u << 1)
#define RS(u) (u << 1 | 1)

  void PushUp(int u) { T(u) = std::min(T(LS(u)), T(RS(u))); }

  void Build(int u = 1, int L = 0, int R = M) {
    if (L + 1 == R) { return T(u) = INF + 1, void(); }
    int M = (L + R) >> 1;
    Build(LS(u), L, M);
    Build(RS(u), M, R);
    PushUp(u);
  }

  void Insert(int x, int v, int u = 1, int L = 0, int R = M) {
    if (R <= x || x < L) { return; }
    if (L + 1 == R) {
      st[L].emplace(disc[v]);
      T(u) = st[L].empty() ? INF + 1 : *st[L].begin();
      return;
    }
    int M = (L + R) >> 1;
    Insert(x, v, LS(u), L, M);
    Insert(x, v, RS(u), M, R);
    PushUp(u);
  }

  void Delete(int x, int v, int u = 1, int L = 0, int R = M) {
    if (R <= x || x < L) { return; }
    if (L + 1 == R) {
      st[L].erase(st[L].find(disc[v]));
      T(u) = st[L].empty() ? INF + 1 : *st[L].begin();
      return;
    }
    int M = (L + R) >> 1;
    Delete(x, v, LS(u), L, M);
    Delete(x, v, RS(u), M, R);
    PushUp(u);
  }

  int Query(int x, int &mi, int u = 1, int L = 0, int R = M) {
    int tmi = std::min(mi, T(u));
    if (tmi > 2 * x - disc[L]) { return mi = tmi, L; }
    if (L + 1 == R) { return R; }
    int M = (L + R) >> 1, ret = Query(x, mi, RS(u), M, R);
    return ret == M ? Query(x, mi, LS(u), L, M) : ret;
  }
}// namespace SegmentTree

int main() {
#ifdef LOCAL
  freopen("task.in", "r", stdin);
  freopen("task.out", "w", stdout);
  freopen("task.err", "w", stderr);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  std::cin >> N >> K >> Q;

  disc.emplace_back(-INF);
  disc.emplace_back(2 * INF + 1);
  for (int i = 0, x, t, l, r; i < N; i++) {
    std::cin >> x >> t >> l >> r, t--;
    events.emplace_back(l, -1, x, t);
    events.emplace_back(r, 1, x, t);
    disc.emplace_back(x);
  }

  for (int i = 0, x, t; i < Q; i++) {
    std::cin >> x >> t, events.emplace_back(t, 0, x, i);
  }

  std::ranges::sort(disc), std::ranges::sort(events);
  disc.erase(std::ranges::unique(disc).begin(), disc.end());
  M = (int) disc.size();

  SegmentTree::Build();
  std::vector<std::multiset<int>> st(K);
  for (int i = 0; i < K; i++) {
    st[i].emplace(0), st[i].emplace(M - 1);
    SegmentTree::Insert(M - 1, 0);
  }

  for (auto [ti, ty, x, t]: events) {
    if (ty == -1) {
      x = int(std::ranges::lower_bound(disc, x) - disc.begin());
      auto it = st[t].lower_bound(x);
      int l = *std::prev(it), r = *it;
      SegmentTree::Delete(r, l);
      SegmentTree::Insert(r, x);
      SegmentTree::Insert(x, l);
      st[t].emplace(x);
    } else if (ty == 1) {
      x = int(std::ranges::lower_bound(disc, x) - disc.begin());
      auto it = st[t].lower_bound(x);
      int l = *std::prev(it), r = *std::next(it);
      SegmentTree::Delete(r, x);
      SegmentTree::Delete(x, l);
      SegmentTree::Insert(r, l);
      st[t].erase(it);
    } else {
      int mi = INF + 1, p = SegmentTree::Query(x, mi);
      ans[t] = std::max(disc[p - 1] - x, x - mi);
    }
  }

  for (int i = 0; i < Q; i++) {
    std::cout << (ans[i] > INF ? -1 : ans[i]) << '\n';
  }

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20