Submission #966869

#	Time	Username	Problem	Language	Result	Execution time	Memory
966869		Soumya1	New Home (APIO18_new_home)	C++17	100 / 100	2005 ms	180700 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 5;
multiset<int> pos[mxN], ss[4 * mxN];
int t[4 * mxN];
vector<int> comp;
int N;
void update(int x, int lx, int rx, int i, int v) {
  if (lx == rx) {
    if (v > 0) ss[x].insert(v);
    else ss[x].erase(ss[x].find(-v));
    t[x] = (ss[x].empty() ? 0 : *prev(ss[x].end()));
    return;
  }
  int mx = (lx + rx) >> 1;
  if (i <= mx) update(x << 1, lx, mx, i, v);
  else update(x << 1 | 1, mx + 1, rx, i, v);
  t[x] = max(t[x << 1], t[x << 1 | 1]);
}
void insert(int l, int r) {
  l = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
  r = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
  update(1, 1, N, l, r);
}
void erase(int l, int r) {
  l = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
  r = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
  update(1, 1, N, l, -r);
}
int get(int x, int lx, int rx, int l, int r) {
  if (l > rx || lx > r) return -1e9;
  if (l <= lx && r >= rx) return t[x];
  int mx = (lx + rx) >> 1;
  return max(get(x << 1, lx, mx, l, r), get(x << 1 | 1, mx + 1, rx, l, r));
}
int query(int x, int lx, int rx, int y, int r = -1e9) {
  if (lx == rx) return lx;
  int mx = (lx + rx) >> 1;
  if (comp[mx] >= y) return query(x << 1, lx, mx, y);
  if (y - comp[mx] - 1 >= max(comp[t[x << 1]], r) - y) return query(x << 1 | 1, mx + 1, rx, y, max(r, comp[t[x << 1]]));
  return query(x << 1, lx, mx, y, r);
}
void testCase() {
  int n, q, k;
  cin >> n >> k >> q;
  vector<array<int, 4>> all;
  comp = {(int) 4e8, (int) -4e8};
  for (int i = 0; i < n; i++) {
    int x, t, a, b;
    cin >> x >> t >> a >> b;
    all.push_back({a, 2, t, x});
    all.push_back({b + 1, 1, t, x});
    comp.push_back(x);
  }
  vector<int> ans(q);
  for (int i = 0; i < q; i++) {
    int l, y;
    cin >> l >> y;
    all.push_back({y, 3, i, l});
  }
  sort(all.begin(), all.end());
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  N = comp.size();
  comp.insert(comp.begin(), -1e9);
  for (int i = 1; i <= k; i++) {
    pos[i].insert((int) -4e8);
    pos[i].insert(4e8);
    insert(-4e8, 4e8);
  }
  for (auto v : all) {
    if (v[1] == 1) {
      auto b = pos[v[2]].upper_bound(v[3]);
      auto s = prev(prev(b));
      erase(*s, v[3]);
      erase(v[3], *b);
      insert(*s, *b);
      pos[v[2]].erase(pos[v[2]].find(v[3]));
    } else if (v[1] == 2) {
      auto b = pos[v[2]].upper_bound(v[3]);
      auto s = prev(b);
      erase(*s, *b);
      pos[v[2]].insert(v[3]);
      insert(*s, v[3]);
      insert(v[3], *b);
    } else {
      if (get(1, 1, N, 1, 1) == N) {
        ans[v[2]] = -1;
        continue;
      }
      int x = query(1, 1, N, v[3]);
      int r = comp[get(1, 1, N, 1, x - 1)];
      int R = r - v[3];
      int L = v[3] - comp[x];
      ans[v[2]] = max(L, R);
    }
  }
  for (int i : ans) cout << i << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  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