Submission #936524

#	Time	Username	Problem	Language	Result	Execution time	Memory
936524		rxlfd314	New Home (APIO18_new_home)	C++17	0 / 100	4961 ms	213300 KiB

new_home

#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 {
  multiset<int> st[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;
    if (ql <= tl && tr <= qr) {
      if (size(st[i]) < 2)
        st[i].insert(v);
      else {
        int first = *begin(st[i]), last = *prev(end(st[i]));
        if (v > last) {
          while (size(st[i]) > 1)
            st[i].erase(prev(end(st[i])));
          st[i].insert(v);
        } else if (v < first) {
          while (size(st[i]) > 1)
            st[i].erase(begin(st[i]));
          st[i].insert(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;
    if (ql <= tl && tr <= qr) {
      if (st[i].count(v))
        st[i].erase(st[i].find(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, bool last, int i = 1, int tl = 0, int tr = size(cmp)-1) {
    int ret = last ? -1 : INT_MAX;
    while (tl < tr) {
      if (size(st[i])) {
        if (last)
          ret = max(ret, *prev(end(st[i])));
        else
          ret = min(ret, *begin(st[i]));
      }
      int tm = tl + tr >> 1;
      if (p <= tm)
        i = lc, tr = tm;
      else
        i = rc, tl = tm + 1;
    }
    if (size(st[i])) {
      if (last)
        ret = max(ret, *prev(end(st[i])));
      else
        ret = min(ret, *begin(st[i]));
    }
    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;
  bool sub3 = true;
  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 = min(x, st_left.qry(i, false));
      int r = max(x, st_right.qry(i, true));
      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 (stderr)

new_home.cpp: In member function 'void ST::insert(int, int, int, int, int, int)':
new_home.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
new_home.cpp: In member function 'void ST::erase(int, int, int, int, int, int)':
new_home.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
new_home.cpp: In member function 'int ST::qry(int, bool, int, int, int)':
new_home.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
new_home.cpp: In lambda function:
new_home.cpp:115:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
new_home.cpp: In lambda function:
new_home.cpp:125:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:93:8: warning: unused variable 'sub3' [-Wunused-variable]
   93 |   bool sub3 = true;
      |        ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20