Submission #49859

#	Time	Username	Problem	Language	Result	Execution time	Memory
49859		zemen	New Home (APIO18_new_home)	C++17	5 / 100	5010 ms	76208 KiB

new_home

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using oset = __gnu_pbds::tree<int, __gnu_pbds::null_type,
        std::less<int>,
        __gnu_pbds::rb_tree_tag,
        __gnu_pbds::tree_order_statistics_node_update>;
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
 
const int base = 1 << 16;
const int inf = 1e9;
oset t[base * 2];
vector<pair<int, int>> xc;
int k;
 
int tget(int l, int r, int v = 1, int cl = 0, int cr = base) {
  if (l <= cl && cr <= r) {
    return t[v].size() - t[v].order_of_key(r);
  }
  if (r <= cl || cr <= l) {
    return 0;
  }
  int cc = (cl + cr) / 2;
  return tget(l, r, v * 2, cl, cc) + tget(l, r, v * 2 + 1, cc, cr);
}
 
int get(int x) {
  int L = -1, R = inf / 2;
  map<pair<int, int>, int> bscache;
  bool ok = false;
  while (L + 1 < R) {
    int C = (L + R) / 2;
    int lb = lower_bound(xc.begin(), xc.end(), pair<int, int>{x - C, -1}) - xc.begin();
    int rb = upper_bound(xc.begin(), xc.end(), pair<int, int>{x + C, inf}) - xc.begin();
 
    auto q = pair<int, int>{lb, rb};
    int cnt;
    if (bscache.count(q)) {
      cnt = bscache[q];
    } else {
      bscache[q] = cnt = tget(lb, rb);
    }
 
    assert(cnt <= k);
    if (cnt >= k) {
      R = C;
      ok = true;
    } else {
      L = C;
    }
  }
  if (!ok) {
    return -1;
  } else {
    return R;
  }
}
 
void tput(int v, int val) {
  v += base;
  while (v >= 1) {
    int ss = -t[v].size();
    t[v].insert(val);
    ss += t[v].size();
    assert(ss == 1);
    v /= 2;
  }
}
 
void tdel(int v, int val) {
  v += base;
  while (v >= 1) {
    int ss = t[v].size();
    t[v].erase(val);
    ss -= t[v].size();
    assert(ss == 1);
    v /= 2;
  }
}
 
set<int> pos[base];
void put(int x, int t, int delta) {
  if (delta == -1) {
    auto it = pos[t].upper_bound(x);
    int val = it == pos[t].end() ? inf + t : *it;
    if (it != pos[t].begin()) {
      --it;
      tdel(*it, val);
      tput(*it, x);
    }
    pos[t].insert(x);
    tput(x, val);
  } else if (delta == 1) {
    assert(pos[t].count(x));
    auto it = pos[t].upper_bound(x);
    int val = it == pos[t].end() ? inf + t : *it;
    tdel(x, val);
    pos[t].erase(x);
    if (it != pos[t].begin()) {
      --it;
      tdel(*it, x);
      tput(*it, val);
    }
  } else {
    assert(false);
  }
}
 
signed main() {
#ifdef LOCAL
  assert(freopen("a.in", "r", stdin));
#endif
  struct Event {
    int tp, tm, x, t, id;
    bool operator<(const Event& e) const {
      if (tm != e.tm) {
        return tm < e.tm;
      }
      return tp < e.tp;
    }
  };
 
  int n, q;
  cin >> n >> k >> q;
  vector<Event> ev;
  for (int i = 0; i < n; ++i) {
    int x, t, a, b;
    cin >> x >> t >> a >> b;
    ev.push_back(Event{-1, a, x, t, i});
    ev.push_back(Event{1, b, x, t, i});
    xc.emplace_back(x, i);
  }
  sort(xc.begin(), xc.end());
  for (int i = 0; i < q; ++i) {
    int l, y;
    cin >> l >> y;
    ev.push_back(Event{0, y, l, -1, i});
  }
  sort(ev.begin(), ev.end());
  vector<int> res(q);
  for (auto& e : ev) {
    if (e.tp == 0) {
      res[e.id] = get(e.x);
    } else {
      auto sx = lower_bound(xc.begin(), xc.end(), pair<int, int>{e.x, e.id}) - xc.begin();
      put(sx, e.t, e.tp);
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << res[i] << '\n';
  }
}

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