Submission #968264

#	Time	Username	Problem	Language	Result	Execution time	Memory
968264		kilkuwu	New Home (APIO18_new_home)	C++17	100 / 100	3113 ms	134108 KiB

new_home

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

struct SegmentTree {
  int n;
  std::vector<int> t;

  SegmentTree(int _n) : n(_n), t(2 * n, -1) {}

  void update(int p, int v) {
    for (t[p += n] = v; p > 1; p >>= 1) {
      t[p >> 1] = std::max(t[p], t[p ^ 1]);
    }
  }

  int query(int l, int r) {
    int ans = -1;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = std::max(ans, t[l++]);
      if (r & 1) ans = std::max(ans, t[--r]);
    }
    return ans;
  }
};

struct Store {
  int x, t, a, b;

  bool operator<(const Store& rhs) const {
    return x < rhs.x;
  }  
};

struct Query {
  int l, y;
};

struct Event {
  int time, id;
  
  bool operator<(const Event& rhs) const {
    return std::make_pair(time, id) < std::make_pair(rhs.time, rhs.id);
  }
};

bool operator<(const Store& s, const int& x) {
  return s.x < x;
}

bool operator<(const int& x, const Store& s) {
  return x < s.x;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, k, q;
  std::cin >> n >> k >> q;

  std::vector<Store> stores(n + 1);
  stores[0].x = -1;
  for (int i = 0; i < n; i++) {
    int x, t, a, b;
    std::cin >> x >> t >> a >> b;
    --t;
    stores[i + 1] = {x, t, a, b};
  }
  std::sort(stores.begin() + 1, stores.end());

  std::vector<int> ans(q);
  std::vector<Query> queries(q);
  for (int i = 0; i < q; i++) {
    std::cin >> queries[i].l >> queries[i].y;
  }

  std::vector<Event> events;
  for (int i = 1; i <= n; i++) {
    events.push_back({stores[i].a, i});
    events.push_back({stores[i].b + 1, i});
  }

  for (int i = 0; i < q; i++) {
    events.push_back({queries[i].y, i + n + 1});
  }

  std::sort(events.begin(), events.end());
  std::vector<std::set<int>> pos(k);

  std::vector<std::multiset<int>> at(n + 1);

  for (int i = 0; i < k; i++) {
    at[0].insert(n + 1);
    pos[i].insert(0);
    pos[i].insert(n + 1);
  }

  dbg("goes here");

  SegmentTree tree(n + 1);
  tree.update(0, n + 1);

  auto rem_at = [&](int id, int v) {
    at[id].erase(at[id].find(v));
    tree.update(id, at[id].empty() ? -1 : *at[id].rbegin());
  };

  auto add_at = [&](int id, int v) {
    at[id].insert(v);
    tree.update(id, at[id].empty() ? -1 : *at[id].rbegin());
  };

  for (auto [time, id] : events) {
    dbg(time, id);
    if (id <= n) {
      auto [x, t, a, b] = stores[id];
      if (time == a) {
        dbg("goes insert", time, id);
        dbg(pos[t], t);
        auto it = pos[t].insert(id).first;
        auto pre = std::prev(it);
        auto nxt = std::next(it);

        dbg(*it, *pre, *nxt);

        rem_at(*pre, *nxt);
        add_at(*pre, *it);
        add_at(*it, *nxt);
      } else {
        auto it = pos[t].find(id);
        auto pre = std::prev(it);
        auto nxt = std::next(it);
        rem_at(*it, *nxt);
        rem_at(*pre, *it);
        add_at(*pre, *nxt);
        pos[t].erase(it);
      }
    } else {
      id -= n + 1;

      int res = -1;
      int lb = 0, rb = 1e8;

      while (lb <= rb) {
        int mb = (lb + rb) / 2;
        int ql = std::lower_bound(stores.begin() + 1, stores.end(), queries[id].l - mb) - stores.begin();
        int qr = std::upper_bound(stores.begin() + 1, stores.end(), queries[id].l + mb) - stores.begin();

        if (tree.query(0, ql) < qr) {
          res = mb;
          rb = mb - 1;
        } else {
          lb = mb + 1;
        }
      }

      ans[id] = res;
    }
  }

  for (int i = 0; i < q; i++) {
    std::cout << ans[i] << nl;
  }
}

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