oj.uz

Submission #966865

# Submission time Handle Problem Language Result Execution time Memory
966865 2024-04-20T13:58:25 Z Soumya1 New Home (APIO18_new_home) C++17
10 / 100
 1788 ms 260144 KB 
#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() ? -1e9 : *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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 71260 KB Output is correct
2 Correct 17 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Runtime error 66 ms 144208 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 71260 KB Output is correct
2 Correct 17 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Runtime error 66 ms 144208 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1236 ms 146924 KB Output is correct
2 Correct 987 ms 134580 KB Output is correct
3 Correct 1788 ms 180052 KB Output is correct
4 Correct 1446 ms 152056 KB Output is correct
5 Correct 971 ms 135288 KB Output is correct
6 Correct 1030 ms 134452 KB Output is correct
7 Correct 1639 ms 179256 KB Output is correct
8 Correct 1363 ms 151540 KB Output is correct
9 Correct 1144 ms 141100 KB Output is correct
10 Correct 1025 ms 135404 KB Output is correct
11 Correct 883 ms 134496 KB Output is correct
12 Correct 942 ms 135268 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 742 ms 260144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 71260 KB Output is correct
2 Correct 17 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Runtime error 66 ms 144208 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 71260 KB Output is correct
2 Correct 17 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Runtime error 66 ms 144208 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -