Submission #937482

#	Time	Username	Problem	Language	Result	Execution time	Memory
937482		rxlfd314	New Home (APIO18_new_home)	C++17	100 / 100	2701 ms	153740 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 {
  priority_queue<int> ins[mxN<<1], die[mxN<<1];
  int st[mxN<<1];
  void build() {
    fill(st, st+2*mxN, INT_MIN);
  }
  void kill(int i) {
    while (size(ins[i]) && size(die[i]) && ins[i].top() == die[i].top())
      ins[i].pop(), die[i].pop();
  } 
  void insert(int i, int v) {
    if (i >= size(cmp))
      return;
    ins[i+=size(cmp)].push(v);
    kill(i);
    st[i] = size(ins[i]) ? ins[i].top() : INT_MIN;
    for (; i > 1; i >>= 1)
      st[i>>1] = max(st[i], st[i^1]);
  }
  void erase(int i, int v) {
    if (i >= size(cmp))
      return;
    die[i+=size(cmp)].push(v);
    kill(i);
    st[i] = size(ins[i]) ? ins[i].top() : INT_MIN;
    for (; i > 1; i >>= 1)
      st[i>>1] = max(st[i], st[i^1]);
  }
  int qry(int ql, int qr) {
    int ret = INT_MIN;
    for (ql += size(cmp), qr += size(cmp)+1; ql < qr; ql >>= 1, qr >>= 1) {
      if (ql & 1)
        ret = max(ret, st[ql++]);
      if (qr & 1)
        ret = max(ret, st[--qr]);
    }
    return ret;
  }
} 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(mi-1, -l); 
    if (ri >= mi)
      st_right.erase(mi, 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(mi-1, -l);
    if (ri >= mi)
      st_right.insert(mi, r);
  };

  vt<int> ans(Q), present(K);
  vt<map<int, int>> positions(K);
  int present_cnt = 0;
  st_left.build();
  st_right.build();
  
  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, size(cmp)-1);
      if (l != INT_MIN)
        l = -l;
      else
        l = x;
      int r = st_right.qry(0, i);
      l = min(l, x);
      r = max(r, 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 (stderr)

new_home.cpp: In lambda function:
new_home.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
new_home.cpp: In lambda function:
new_home.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~

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