oj.uz

Submission #892134

# Submission time Handle Problem Language Result Execution time Memory
892134 2023-12-25T00:34:03 Z MilosMilutinovic New Home (APIO18_new_home) C++14
33 / 100
 4919 ms 362380 KB 
#include <bits/stdc++.h>
 
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> x(n);
  vector<int> t(n);
  vector<int> a(n);
  vector<int> b(n);
  map<pair<int, int>, vector<pair<int, int>>> mp;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> t[i] >> a[i] >> b[i];
    --t[i]; ++b[i];
    mp[{x[i], t[i]}].emplace_back(a[i], b[i]);
  }
  vector<int> new_x;
  vector<int> new_t;
  vector<int> new_a;
  vector<int> new_b;
  for (auto& p : mp) {
    vector<pair<int, int>> v = p.second;
    sort(v.begin(), v.end());
    int sz = (int) v.size();
    for (int i = 0; i < sz; i++) {
      int ptr = i;
      int mx = v[i].second;
      while (ptr + 1 < sz && v[ptr + 1].first < mx) {
        ptr += 1;
        mx = max(mx, v[ptr].second);
      }
      new_x.push_back(p.first.first);
      new_t.push_back(p.first.second);
      new_a.push_back(v[i].first);
      new_b.push_back(mx);
      i = ptr;
    }
  }
  x = new_x;
  t = new_t;
  a = new_a;
  b = new_b;
  n = (int) x.size();
  vector<int> l(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    cin >> l[i] >> y[i];
  }
  vector<int> xs(1, 1e9);
  for (int i = 0; i < n; i++) {
    xs.push_back(a[i]);
    xs.push_back(b[i]);
  }
  for (int i = 0; i < q; i++) {
    xs.push_back(y[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
    b[i] = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
  }
  for (int i = 0; i < q; i++) {
    y[i] = (int) (lower_bound(xs.begin(), xs.end(), y[i]) - xs.begin());
  }
  int T = (int) xs.size();
  vector<vector<int>> ids(T);
  for (int i = 0; i < n; i++) {
    ids[a[i]].push_back(i);
    ids[b[i]].push_back(~i);
  }
  const int inf = (int) 1e9;
  vector<multiset<tuple<int, int, int>>> open(k);
  vector<array<int, 4>> ev;
  vector<multiset<int>> my(k);
  auto Insert = [&](int t, int x, int y) {
    if (my[t].find(x) != my[t].end()) {
      assert(false);
    }
    auto ptr = my[t].lower_bound(x);
    if (ptr != my[t].begin() && ptr != my[t].end()) {
      auto it = open[t].lower_bound({*prev(ptr), *ptr, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    } else if (ptr != my[t].begin()) {
      auto it = open[t].lower_bound({*prev(ptr), inf, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    } else if (ptr != my[t].end()) {
      auto it = open[t].lower_bound({-inf, *ptr, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    }
    if (ptr != my[t].end()) {
      open[t].emplace(x, *ptr, y);
    } else {
      open[t].emplace(x, inf, y);
    }
    if (ptr != my[t].begin()) {
      ptr = prev(ptr);
      open[t].emplace(*ptr, x, y);
    } else {
      open[t].emplace(-inf, x, y);
    }
    my[t].insert(x);
  };
  auto Remove = [&](int t, int x, int y) {
    assert(my[t].find(x) != my[t].end());
    auto ptr = my[t].lower_bound(x);
    if (ptr != prev(my[t].end())) {
      auto it = open[t].lower_bound({x, *next(ptr), -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    } else {
      auto it = open[t].lower_bound({x, inf, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    }
    if (ptr != my[t].begin()) {
      auto it = open[t].lower_bound({*prev(ptr), x, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    } else {
      auto it = open[t].lower_bound({-inf, x, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open[t].erase(it);
    }
    if (ptr != my[t].begin() && ptr != prev(my[t].end())) {
      open[t].emplace(*prev(ptr), *next(ptr), y);
    } else if (ptr != my[t].begin()) {
      open[t].emplace(*prev(ptr), inf, y);
    } else if (ptr != prev(my[t].end())) {
      open[t].emplace(-inf, *next(ptr), y);
    }
    my[t].erase(my[t].find(x));
  }; 
  for (int i = 0; i < T; i++) {
    sort(ids[i].begin(), ids[i].end());
    for (int j : ids[i]) {
      if (j >= 0) {
        Insert(t[j], x[j], i);
      } else {
        j = ~j;
        Remove(t[j], x[j], i);
      }
    }
  }
  for (int i = 0; i < k; i++) {
    for (auto& p : open[i]) {
      ev.push_back({get<0>(p), get<1>(p), get<2>(p), T - 1});
    }
  }
  vector<vector<int>> qs(T);
  for (int i = 0; i < q; i++) {
    qs[y[i]].push_back(i);
  }
  vector<pair<int, int>> min_with;
  vector<pair<int, int>> max_with;
  for (auto& p : ev) {
    int L = p[0];
    int R = p[1];
    int mid = (L + R) / 2;
    min_with.emplace_back(L, mid);
    max_with.emplace_back(R, mid + (L % 2 != R % 2));
  }
  sort(min_with.begin(), min_with.end(), [&](pair<int, int> p, pair<int, int> q) {
    return p.second > q.second;
  });
  sort(max_with.begin(), max_with.end(), [&](pair<int, int> p, pair<int, int> q) {
    return p.second < q.second;
  });
  map<pair<int, int>, int> idx_mn;
  map<pair<int, int>, int> idx_mx;
  int sz = (int) ev.size();
  for (int i = 0; i < sz; i++) {
    idx_mn[min_with[i]] = i;
  }
  for (int i = 0; i < sz; i++) {
    idx_mx[max_with[i]] = i;
  }
  vector<vector<int>> qs_mn(T);
  vector<vector<int>> qs_mx(T);
  for (int i = 0; i < sz; i++) {
    int L = ev[i][0];
    int R = ev[i][1];
    int from = ev[i][2];
    int to = ev[i][3];
    int mid = (L + R) / 2;
    {
      int idx = idx_mn[{L, mid}];
      qs_mn[from].push_back(idx);
      qs_mn[to].push_back(~idx);
    }
    {
      int idx = idx_mx[{R, mid + (L % 2 != R % 2)}];
      qs_mx[from].push_back(idx);
      qs_mx[to].push_back(~idx);
    }
  }
  vector<int> mn(4 * sz);
  vector<int> mx(4 * sz);
  function<void(int, int, int)> Build = [&](int x, int l, int r) {
    mn[x] = inf;
    mx[x] = -inf;
    if (l == r) {
      return;
    }
    int mid = l + r >> 1;
    Build(x << 1, l, mid);
    Build(x << 1 | 1, mid + 1, r);
  };
  function<void(int, int, int, int, int)> ModifyMin = [&](int x, int l, int r, int p, int v) {
    if (l == r) {
      mn[x] = v;
      return;
    }
    int mid = l + r >> 1;
    if (p <= mid) {
      ModifyMin(x << 1, l, mid, p, v);
    } else {
      ModifyMin(x << 1 | 1, mid + 1, r, p, v);
    }
    mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
  };
  function<void(int, int, int, int, int)> ModifyMax = [&](int x, int l, int r, int p, int v) {
    if (l == r) {
      mx[x] = v;
      return;
    }
    int mid = l + r >> 1;
    if (p <= mid) {
      ModifyMax(x << 1, l, mid, p, v);
    } else {
      ModifyMax(x << 1 | 1, mid + 1, r, p, v);
    }
    mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
  };
  auto ChangeMin = [&](int p, int v) {
    ModifyMin(1, 0, sz - 1, p, v);
  };
  auto ChangeMax = [&](int p, int v) {
    ModifyMax(1, 0, sz - 1, p, v);
  };
  function<int(int, int, int, int, int)> query_max = [&](int x, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll) {
      return -inf;
    }
    if (ll <= l && r <= rr) {
      return mx[x];
    }
    int mid = l + r >> 1;
    return max(query_max(x << 1, l, mid, ll, rr), query_max(x << 1 | 1, mid + 1, r, ll, rr));
  };
  function<int(int, int, int, int, int)> query_min = [&](int x, int l, int r, int ll, int rr) {
    if (l > r || l > rr || r < ll) {
      return inf;
    }
    if (ll <= l && r <= rr) {
      return mn[x];
    }
    int mid = l + r >> 1;
    return min(query_min(x << 1, l, mid, ll, rr), query_min(x << 1 | 1, mid + 1, r, ll, rr));
  };
  auto get_max = [&](int l, int r) {
    return query_max(1, 0, sz - 1, l, r);
  };
  auto get_min = [&](int l, int r) {
    return query_min(1, 0, sz - 1, l, r);
  };
  Build(1, 0, sz - 1);
  vector<int> res(q);
  for (int i = 0; i < T; i++) {
    for (int j : qs_mn[i]) {
      if (j >= 0) {
        ChangeMin(j, min_with[j].first);
      } else {
        j = ~j;
        ChangeMin(j, inf);
      }
    }
    for (int j : qs_mx[i]) {
      if (j >= 0) {
        ChangeMax(j, max_with[j].first);
      } else {
        j = ~j;
        ChangeMax(j, -inf);
      }
    }
    for (int j : qs[i]) {
      {
        int low = 0, high = sz - 1, pos = -1;
        while (low <= high) {
          int mid = low + high >> 1;
          if (min_with[mid].second >= l[j]) {
            pos = mid;
            low = mid + 1;
          } else {
            high = mid - 1;
          }
        }
        if (pos != -1) {
          res[j] = max(res[j], l[j] - get_min(0, pos));
        }
      }
      {
        int low = 0, high = sz - 1, pos = -1;
        while (low <= high) {
          int mid = low + high >> 1;
          if (max_with[mid].second <= l[j]) {
            pos = mid;
            low = mid + 1;
          } else {
            high = mid - 1;
          }
        }
        if (pos != -1) {
          res[j] = max(res[j], get_max(0, pos) - l[j]);
        }
      }
    }
  }
  vector<vector<int>> qs_type(T);
  for (int i = 0; i < n; i++) {
    qs_type[a[i]].push_back(t[i]);
    qs_type[b[i]].push_back(~t[i]);
  }
  int bal = 0;
  vector<int> cnt(k);
  for (int i = 0; i < T; i++) {
    for (int j : qs_type[i]) {
      if (j >= 0) {
        cnt[j] += 1;
        if (cnt[j] == 1) {
          bal += 1;
        }
      } else {
        j = ~j;
        cnt[j] -= 1;
        if (cnt[j] == 0) {
          bal -= 1;
        }
      }
    }
    for (int j : qs[i]) {
      if (bal != k) {
        res[j] = -1;
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10


2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1 1
*/

Compilation message

new_home.cpp: In lambda function:
new_home.cpp:211:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  211 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:220:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  220 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:233:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  233 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:254:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  254 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:264:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  264 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:296:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  296 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:311:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  311 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2724 ms 255156 KB Output is correct
2 Correct 2303 ms 254524 KB Output is correct
3 Correct 1676 ms 270892 KB Output is correct
4 Correct 2638 ms 262244 KB Output is correct
5 Correct 2503 ms 251188 KB Output is correct
6 Correct 2246 ms 255760 KB Output is correct
7 Correct 1607 ms 272152 KB Output is correct
8 Correct 2656 ms 258460 KB Output is correct
9 Correct 2768 ms 254496 KB Output is correct
10 Correct 2441 ms 255164 KB Output is correct
11 Correct 1971 ms 251904 KB Output is correct
12 Correct 2065 ms 250872 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4919 ms 346908 KB Output is correct
2 Correct 186 ms 19612 KB Output is correct
3 Correct 4537 ms 360732 KB Output is correct
4 Correct 3438 ms 335644 KB Output is correct
5 Correct 4620 ms 350212 KB Output is correct
6 Correct 4511 ms 345108 KB Output is correct
7 Correct 4389 ms 359376 KB Output is correct
8 Correct 4379 ms 360636 KB Output is correct
9 Correct 3251 ms 343444 KB Output is correct
10 Correct 4549 ms 347152 KB Output is correct
11 Correct 4862 ms 355132 KB Output is correct
12 Correct 4904 ms 362380 KB Output is correct
13 Correct 2293 ms 351432 KB Output is correct
14 Correct 2238 ms 347372 KB Output is correct
15 Correct 2567 ms 356648 KB Output is correct
16 Correct 2785 ms 360464 KB Output is correct
17 Correct 2628 ms 352416 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -