oj.uz

Submission #892132

# Submission time Handle Problem Language Result Execution time Memory
892132 2023-12-24T23:54:08 Z MilosMilutinovic New Home (APIO18_new_home) C++14
10 / 100
 5000 ms 345340 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) {
    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.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;
}

/*
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:208:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  208 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:217:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  217 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:230:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  230 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:251:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  251 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:261:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  261 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:293:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  293 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:308:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  308 |           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 3146 ms 253524 KB Output is correct
2 Correct 2335 ms 252988 KB Output is correct
3 Correct 1793 ms 257836 KB Output is correct
4 Correct 3036 ms 253192 KB Output is correct
5 Correct 2662 ms 252676 KB Output is correct
6 Correct 2386 ms 253864 KB Output is correct
7 Correct 1728 ms 258252 KB Output is correct
8 Correct 3068 ms 254800 KB Output is correct
9 Correct 3157 ms 254524 KB Output is correct
10 Correct 2549 ms 252124 KB Output is correct
11 Correct 2094 ms 249016 KB Output is correct
12 Correct 2329 ms 252028 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 345340 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 -