oj.uz

Submission #892103

# Submission time Handle Problem Language Result Execution time Memory
892103 2023-12-24T22:21:57 Z MilosMilutinovic New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 290072 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);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> t[i] >> a[i] >> b[i];
    --t[i]; ++b[i];
  }
  vector<int> l(q);
  vector<int> y(q);
  for (int i = 0; i < n; 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++) {
    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 (int) -1e9;
    }
    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 (int) 1e9;
    }
    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:175:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  175 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:184:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  184 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:197:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  197 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:218:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  218 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:228:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  228 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:260:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  260 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:275:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  275 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4957 ms 257868 KB Output is correct
2 Correct 4565 ms 264720 KB Output is correct
3 Correct 3183 ms 235648 KB Output is correct
4 Correct 4652 ms 255840 KB Output is correct
5 Correct 4065 ms 267632 KB Output is correct
6 Correct 4502 ms 264224 KB Output is correct
7 Correct 3030 ms 233488 KB Output is correct
8 Correct 4041 ms 254152 KB Output is correct
9 Correct 4146 ms 266180 KB Output is correct
10 Correct 4383 ms 266724 KB Output is correct
11 Incorrect 2344 ms 259788 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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