oj.uz

답안 #892113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
892113 2023-12-24T22:58:36 Z MilosMilutinovic 새 집 (APIO18_new_home) C++14
10 / 100
 5000 ms 345600 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++) {
    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:204:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  204 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:213:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  213 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:226:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  226 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:247:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  247 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:257:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  257 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:289:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  289 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:304:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  304 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3092 ms 282512 KB Output is correct
2 Correct 2370 ms 293232 KB Output is correct
3 Correct 1795 ms 260232 KB Output is correct
4 Correct 2949 ms 277776 KB Output is correct
5 Correct 2462 ms 289804 KB Output is correct
6 Correct 2375 ms 289804 KB Output is correct
7 Correct 1788 ms 260724 KB Output is correct
8 Correct 2999 ms 278012 KB Output is correct
9 Correct 2993 ms 289520 KB Output is correct
10 Correct 2596 ms 290400 KB Output is correct
11 Correct 2105 ms 288396 KB Output is correct
12 Correct 2290 ms 302116 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5046 ms 345600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 -