oj.uz

Submission #892119

# Submission time Handle Problem Language Result Execution time Memory
892119 2023-12-24T23:25:17 Z MilosMilutinovic New Home (APIO18_new_home) C++14
10 / 100
 5000 ms 346756 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;
  multiset<tuple<int, int, int>> open;
  vector<array<int, 4>> ev;
  vector<multiset<int>> my(k);
  auto Insert = [&](int t, int x, int y) {
    auto ptr = my[t].lower_bound(x);
    if (ptr != my[t].begin() && ptr != my[t].end()) {
      auto it = open.lower_bound({*prev(ptr), *ptr, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    } else if (ptr != my[t].begin()) {
      auto it = open.lower_bound({*prev(ptr), inf, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    } else if (ptr != my[t].end()) {
      auto it = open.lower_bound({-inf, *ptr, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    }
    if (ptr != my[t].end()) {
      open.emplace(x, *ptr, y);
    } else {
      open.emplace(x, inf, y);
    }
    if (ptr != my[t].begin()) {
      ptr = prev(ptr);
      open.emplace(*ptr, x, y);
    } else {
      open.emplace(-inf, x, y);
    }
    my[t].insert(x);
  };
  auto Remove = [&](int t, int x, int y) {
    auto ptr = my[t].lower_bound(x);
    if (ptr != prev(my[t].end())) {
      auto it = open.lower_bound({x, *next(ptr), -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    } else {
      auto it = open.lower_bound({x, inf, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    }
    if (ptr != my[t].begin()) {
      auto it = open.lower_bound({*prev(ptr), x, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    } else {
      auto it = open.lower_bound({-inf, x, -1});
      ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
      open.erase(it);
    }
    if (ptr != my[t].begin() && ptr != prev(my[t].end())) {
      open.emplace(*prev(ptr), *next(ptr), y);
    } else if (ptr != my[t].begin()) {
      open.emplace(*prev(ptr), inf, y);
    } else if (ptr != prev(my[t].end())) {
      open.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 (auto& p : open) {
    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;
}

Compilation message

new_home.cpp: In lambda function:
new_home.cpp:205:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  205 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:214:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  214 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:227:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  227 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:248:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  248 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:258:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  258 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:290:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  290 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:305:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  305 |           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 3016 ms 252444 KB Output is correct
2 Correct 2366 ms 252940 KB Output is correct
3 Correct 1728 ms 262276 KB Output is correct
4 Correct 2909 ms 252124 KB Output is correct
5 Correct 2500 ms 251780 KB Output is correct
6 Correct 2296 ms 255124 KB Output is correct
7 Correct 1668 ms 258460 KB Output is correct
8 Correct 2904 ms 252344 KB Output is correct
9 Correct 2949 ms 256016 KB Output is correct
10 Correct 2491 ms 252604 KB Output is correct
11 Correct 2009 ms 250412 KB Output is correct
12 Correct 2211 ms 252364 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5044 ms 346756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

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 -