oj.uz

Submission #892145

# Submission time Handle Problem Language Result Execution time Memory
892145 2023-12-25T01:10:35 Z MilosMilutinovic New Home (APIO18_new_home) C++14
10 / 100
 3059 ms 248772 KB 
#include <bits/stdc++.h>
 
using namespace std;

const int N = (int) 4e6;

const int inf = (int) 1e9;

int mn[N], mx[N], sz;

void 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);
}

void 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]);
}

void 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]);
}

void ChangeMin(int p, int v) {
  ModifyMin(1, 0, sz - 1, p, v);
}

void ChangeMax(int p, int v) {
  ModifyMax(1, 0, sz - 1, p, v);
}

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));
}

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));
}

int get_max(int l, int r) {
  return query_max(1, 0, sz - 1, l, r);
}

int get_min(int l, int r) {
  return query_min(1, 0, sz - 1, l, r);
}

vector<multiset<tuple<int, int, int>>> open;
vector<array<int, 4>> ev;
vector<multiset<int>> my;

void 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[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);
}

void Remove(int t, int x, int y) {
  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));
}

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);
  }
  open.resize(k);
  my.resize(k);
  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;
  });
  sz = (int) ev.size();
  vector<int> order_mn(sz);
  iota(order_mn.begin(), order_mn.end(), 0);
  sort(order_mn.begin(), order_mn.end(), [&](int i, int j) {
    return (ev[i][0] + ev[i][1]) / 2 > (ev[j][0] + ev[j][1]) / 2;
  });
  vector<int> order_mx(sz);
  iota(order_mx.begin(), order_mx.end(), 0);
  sort(order_mx.begin(), order_mx.end(), [&](int i, int j) {
    return (ev[i][0] + ev[i][1]) / 2 + (ev[i][0] % 2 != ev[i][1]) < 
           (ev[j][0] + ev[j][1]) / 2 + (ev[j][0] % 2 != ev[j][1]);
  });
  vector<int> idx_mn(sz);
  vector<int> idx_mx(sz);
  for (int i = 0; i < sz; i++) {
    idx_mn[order_mn[i]] = i;
    idx_mx[order_mx[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[i];
      qs_mn[from].push_back(idx);
      qs_mn[to].push_back(~idx);
    }
    {
      int idx = idx_mx[i];
      qs_mx[from].push_back(idx);
      qs_mx[to].push_back(~idx);
    }
  }
  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 function 'void Build(int, int, int)':
new_home.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'void ModifyMin(int, int, int, int, int)':
new_home.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'void ModifyMax(int, int, int, int, int)':
new_home.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'int query_max(int, int, int, int, int)':
new_home.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'int query_min(int, int, int, int, int)':
new_home.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:283:9: warning: unused variable 'mid' [-Wunused-variable]
  283 |     int mid = (L + R) / 2;
      |         ^~~
new_home.cpp:318:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  318 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:333:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  333 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Incorrect 2 ms 2396 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 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Incorrect 2 ms 2396 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 1833 ms 196288 KB Output is correct
2 Correct 1704 ms 191840 KB Output is correct
3 Correct 1199 ms 213260 KB Output is correct
4 Correct 1716 ms 200884 KB Output is correct
5 Correct 1739 ms 192164 KB Output is correct
6 Correct 1632 ms 192516 KB Output is correct
7 Correct 1202 ms 212304 KB Output is correct
8 Correct 1753 ms 201656 KB Output is correct
9 Correct 1840 ms 193844 KB Output is correct
10 Correct 1811 ms 192636 KB Output is correct
11 Correct 1288 ms 190548 KB Output is correct
12 Correct 1413 ms 192264 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3059 ms 248772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Incorrect 2 ms 2396 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 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Incorrect 2 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -