oj.uz

Submission #936587

# Submission time Handle Problem Language Result Execution time Memory
936587 2024-03-02T09:20:37 Z rxlfd314 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 319760 KB 
#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
constexpr int mxN = 300000;
int N, K, Q;
vt<int> cmp;
 
struct ST {
  priority_queue<int> st[mxN<<2], die[mxN<<2];
  #define lc i << 1
  #define rc lc | 1
  void insert(int ql, int qr, int v, int i = 1, int tl = 0, int tr = size(cmp)-1) {
    if (tl > qr || tr < ql)
      return;
    while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
      st[i].pop(), die[i].pop();
    if (ql <= tl && tr <= qr)
      st[i].push(v);
    else {
      int tm = tl + tr >> 1;
      insert(ql, qr, v, lc, tl, tm);
      insert(ql, qr, v, rc, tm+1, tr);
    }
  }
  void erase(int ql, int qr, int v, int i = 1, int tl = 0, int tr = size(cmp)-1) {
    if (tl > qr || tr < ql)
      return;
    while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
      st[i].pop(), die[i].pop();
    if (ql <= tl && tr <= qr)
      die[i].push(v);
    else {
      int tm = tl + tr >> 1;
      erase(ql, qr, v, lc, tl, tm);
      erase(ql, qr, v, rc, tm+1, tr);
    }
  }
  int qry(int p, int i = 1, int tl = 0, int tr = size(cmp)-1) {
    int ret = INT_MIN;
    while (tl < tr) {
      while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
        st[i].pop(), die[i].pop();
      if (size(st[i]))
        ret = max(ret, st[i].top());
      int tm = tl + tr >> 1;
      if (p <= tm)
        i = lc, tr = tm;
      else
        i = rc, tl = tm + 1;
    }
    while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
      st[i].pop(), die[i].pop();
    if (size(st[i]))
      ret = max(ret, st[i].top());
    return ret;
  }
#undef lc
#undef rc
} st_left, st_right;

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> K >> Q;
  vt<ari4> events;
  FOR(i, 0, N-1) {
    int x, t, a, b;
    cin >> x >> t >> a >> b, t--;
    events.push_back({a, 0, x, t}); // time, (0 = insert, 1 = remove, 2 = is year), location, type
    events.push_back({b+1, 1, x, t});
  }
  FOR(i, 0, Q-1) {
    int year, x;
    cin >> x >> year;
    events.push_back({year, 2, x, i}); // time, is year, location, query index
    cmp.push_back(x);
  }
  sort(all(cmp));
  cmp.erase(unique(all(cmp)), end(cmp));
  sort(all(events));

  auto ind = [&](int v) {
    return lower_bound(all(cmp), v) - begin(cmp);
  };
  auto erase = [&](int l, int r) {
    assert(l + r + 1 >= 0);
    int m = l + r + 1 >> 1;
    int li = ind(l), ri = ind(r), mi = ind(m);
    ri -= cmp[ri] > r;
    if (mi - 1 >= li)
      st_left.erase(li, mi-1, l); 
    if (ri >= mi)
      st_right.erase(mi, ri, -r);
  };
  auto insert = [&](int l, int r) {
    assert(l + r + 1 >= 0);
    int m = l + r + 1 >> 1;
    int li = ind(l), ri = ind(r), mi = ind(m);
    ri -= cmp[ri] > r;
    if (mi - 1 >= li)
      st_left.insert(li, mi-1, l);
    if (ri >= mi)
      st_right.insert(mi, ri, -r);
  };

  vt<int> ans(Q), present(K);
  vt<map<int, int>> positions(K);
  int present_cnt = 0;
  for (auto &[t, is_query, x, type] : events) {
    if (is_query == 2) {
      if (present_cnt < K) {
        ans[type] = -1;
        continue;
      }
      int i = ind(x);
      int l = st_left.qry(i);
      if (l == INT_MIN)
        l = x;
      int r = st_right.qry(i);
      if (r != INT_MIN)
        r = -r;
      r = max(r, x);
      l = min(l, x);
      ans[type] = max(r - x, x - l);
#ifdef DEBUG
      cout << "at time " << t << " answer for " << x << " is:\n";
      cout << "L: " << l << '\n';
      cout << "R: " << r << '\n';
#endif
    } else if (is_query) {
      auto &xs = positions[type];
      if (xs[x] == 1) {
        auto it = xs.find(x);
        int l = it != begin(xs) ? prev(it)->first : -1;
        int r = next(it) != end(xs) ? next(it)->first : INT_MAX;
        xs.erase(it);
        if (l >= 0)
          erase(l, x);
        else
          erase(-x, x);
        if (r < INT_MAX)
          erase(x, r); 
        else
          erase(x, INT_MAX - x - 1);

        if (l >= 0 && r < INT_MAX)
          insert(l, r);
        else if (l >= 0)
          insert(l, INT_MAX - l - 1);
        else if (r < INT_MAX)
          insert(-r, r);
      } else {
        xs[x]--;
      }
      present_cnt -= --present[type] == 0;
    } else {
      auto &xs = positions[type];
      if (xs[x])
        xs[x]++;
      else {
        xs[x] = 1;
        auto it = xs.find(x);
        int l = it != begin(xs) ? prev(it)->first : -1;
        int r = next(it) != end(xs) ? next(it)->first : INT_MAX;
        if (l >= 0 && r < INT_MAX)
          erase(l, r);
        else if (l >= 0)
          erase(l, INT_MAX - l - 1);
        else if (r < INT_MAX)
          erase(-r, r);

        if (l >= 0)
          insert(l, x);
        else
          insert(-x, x);
        if (r < INT_MAX)
          insert(x, r);
        else
          insert(x, INT_MAX - x - 1);
      }
      present_cnt += ++present[type] == 1;
    }
  }

  for (int &i : ans)
    cout << i << '\n';
}

Compilation message

new_home.cpp: In member function 'void ST::insert(int, int, int, int, int, int)':
new_home.cpp:31:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
new_home.cpp: In member function 'void ST::erase(int, int, int, int, int, int)':
new_home.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
new_home.cpp: In member function 'int ST::qry(int, int, int, int)':
new_home.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
new_home.cpp: In lambda function:
new_home.cpp:100:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
new_home.cpp: In lambda function:
new_home.cpp:110:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 150724 KB Output is correct
2 Correct 41 ms 150608 KB Output is correct
3 Correct 37 ms 150636 KB Output is correct
4 Incorrect 38 ms 150612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 150724 KB Output is correct
2 Correct 41 ms 150608 KB Output is correct
3 Correct 37 ms 150636 KB Output is correct
4 Incorrect 38 ms 150612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 150724 KB Output is correct
2 Correct 41 ms 150608 KB Output is correct
3 Correct 37 ms 150636 KB Output is correct
4 Incorrect 38 ms 150612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 150724 KB Output is correct
2 Correct 41 ms 150608 KB Output is correct
3 Correct 37 ms 150636 KB Output is correct
4 Incorrect 38 ms 150612 KB Output isn't correct
5 Halted 0 ms 0 KB -