Submission #49857

#	Time	Username	Problem	Language	Result	Execution time	Memory
49857		zemen	New Home (APIO18_new_home)	C++17	5 / 100	5071 ms	156412 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

mt19937 rr(133337);
struct Node {
  int x, y, cnt;
  Node* l;
  Node* r;

  Node(int x) : x(x), y(rr()), cnt(1), l(nullptr), r(nullptr) {}
};

int cnt(Node* t) {
  return t ? t->cnt : 0;
}

void update(Node* t) {
  if (t) {
    t->cnt = cnt(t->l) + cnt(t->r) + 1;
  }
}

void split(Node* t, Node*& l, Node*& r, int x) {
  if (!t) {
    l = r = nullptr;
    return;
  }
  if (t->x >= x) {
    split(t->l, l, t->l, x);
    r = t;
  } else {
    split(t->r, t->r, r, x);
    l = t;
  }
  update(t);
}

void merge(Node*& t, Node* l, Node* r) {
  if (!l) {
    t = r;
  } else if (!r) {
    t = l;
  } else {
    if (l->y > r->y) {
      merge(l->r, l->r, r);
      t = l;
    } else {
      merge(r->l, l, r->l);
      t = r;
    }
    update(t);
  }
}

void ins(Node*& t, int x) {
  Node* A;
  split(t, t, A, x);
  merge(t, t, new Node(x));
  merge(t, t, A);
}

void del(Node*& t, int x) {
  Node* A;
  Node* B;
  split(t, t, B, x + 1);
  split(t, A, t, x);
  assert(t);
  delete t;
  merge(t, A, B);
}

int order_of_key(Node*& t, int x) {
  Node* A;
  split(t, t, A, x);
  int res = cnt(t);
  merge(t, t, A);
  return res;
}

const int base = 1 << 19;
const int inf = 1e9;
Node* 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) {
    int res = cnt(t[v]) - order_of_key(t[v], r);
    return res;
  }
  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) {
    ins(t[v], val);
    v /= 2;
  }
}

void tdel(int v, int val) {
  v += base;
  while (v >= 1) {
    del(t[v], val);
    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