Submission #936543

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
936543	2024-03-02T07:09:33 Z	rxlfd314	New Home (APIO18_new_home)	C++17	10 / 100	1789 ms	219312 KB

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;
  map<int, vt<int>> bruh;
  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});
    bruh[t].push_back(x);
  }
  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);
  };
  for (auto &[t, pos] : bruh) {
    sort(all(pos));
    insert(-pos[0], pos[0]);
    FOR(i, 1, size(pos)-1)
      insert(pos[i-1], pos[i]);
    insert(pos.back(), INT_MAX - pos.back() - 1);
  }

  vt<int> ans(Q), present(K);
  vt<map<int, int>> positions(K);
  int present_cnt = size(bruh);
  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

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:117:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |     int m = l + r + 1 >> 1;
      |             ~~~~~~^~~
new_home.cpp: In lambda function:
new_home.cpp:127:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |     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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	113152 KB	Output is correct
2	Incorrect	23 ms	112984 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	113152 KB	Output is correct
2	Incorrect	23 ms	112984 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1740 ms	195752 KB	Output is correct
2	Correct	857 ms	184024 KB	Output is correct
3	Correct	1484 ms	219312 KB	Output is correct
4	Correct	1786 ms	213748 KB	Output is correct
5	Correct	534 ms	148328 KB	Output is correct
6	Correct	738 ms	171748 KB	Output is correct
7	Correct	1228 ms	219056 KB	Output is correct
8	Correct	1651 ms	212648 KB	Output is correct
9	Correct	1789 ms	206836 KB	Output is correct
10	Correct	1498 ms	204340 KB	Output is correct
11	Correct	843 ms	192740 KB	Output is correct
12	Correct	1254 ms	203160 KB	Output is correct