oj.uz

Submission #937469

# Submission time Handle Problem Language Result Execution time Memory
937469 2024-03-04T06:23:19 Z rxlfd314 New Home (APIO18_new_home) C++17
0 / 100
 2087 ms 149916 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> 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) {
    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) {
    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 && l >= 0)
      st_left.erase(mi-1, -l); 
    if (ri >= mi && r <= 1e8)
      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 && l >= 0)
      st_left.insert(mi-1, -l);
    if (ri >= mi && r <= 1e8)
      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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80096 KB Output is correct
2 Correct 17 ms 80084 KB Output is correct
3 Correct 19 ms 80216 KB Output is correct
4 Correct 17 ms 80216 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80220 KB Output is correct
7 Correct 17 ms 80220 KB Output is correct
8 Correct 18 ms 80344 KB Output is correct
9 Correct 17 ms 80220 KB Output is correct
10 Correct 19 ms 80336 KB Output is correct
11 Correct 20 ms 80220 KB Output is correct
12 Correct 18 ms 80356 KB Output is correct
13 Correct 17 ms 80220 KB Output is correct
14 Correct 17 ms 80304 KB Output is correct
15 Correct 17 ms 80188 KB Output is correct
16 Correct 18 ms 80472 KB Output is correct
17 Correct 18 ms 80220 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 18 ms 80220 KB Output is correct
20 Correct 18 ms 80220 KB Output is correct
21 Correct 17 ms 80388 KB Output is correct
22 Correct 17 ms 80312 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 18 ms 80220 KB Output is correct
25 Correct 18 ms 80388 KB Output is correct
26 Correct 21 ms 80216 KB Output is correct
27 Correct 17 ms 80220 KB Output is correct
28 Incorrect 18 ms 80220 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80096 KB Output is correct
2 Correct 17 ms 80084 KB Output is correct
3 Correct 19 ms 80216 KB Output is correct
4 Correct 17 ms 80216 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80220 KB Output is correct
7 Correct 17 ms 80220 KB Output is correct
8 Correct 18 ms 80344 KB Output is correct
9 Correct 17 ms 80220 KB Output is correct
10 Correct 19 ms 80336 KB Output is correct
11 Correct 20 ms 80220 KB Output is correct
12 Correct 18 ms 80356 KB Output is correct
13 Correct 17 ms 80220 KB Output is correct
14 Correct 17 ms 80304 KB Output is correct
15 Correct 17 ms 80188 KB Output is correct
16 Correct 18 ms 80472 KB Output is correct
17 Correct 18 ms 80220 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 18 ms 80220 KB Output is correct
20 Correct 18 ms 80220 KB Output is correct
21 Correct 17 ms 80388 KB Output is correct
22 Correct 17 ms 80312 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 18 ms 80220 KB Output is correct
25 Correct 18 ms 80388 KB Output is correct
26 Correct 21 ms 80216 KB Output is correct
27 Correct 17 ms 80220 KB Output is correct
28 Incorrect 18 ms 80220 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1303 ms 149848 KB Output is correct
2 Correct 878 ms 142028 KB Output is correct
3 Correct 635 ms 146092 KB Output is correct
4 Correct 1238 ms 149916 KB Output is correct
5 Incorrect 739 ms 133840 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2087 ms 146224 KB Output is correct
2 Correct 269 ms 104168 KB Output is correct
3 Correct 1843 ms 140800 KB Output is correct
4 Correct 691 ms 149192 KB Output is correct
5 Correct 1558 ms 147204 KB Output is correct
6 Correct 1374 ms 147892 KB Output is correct
7 Incorrect 1436 ms 137688 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80096 KB Output is correct
2 Correct 17 ms 80084 KB Output is correct
3 Correct 19 ms 80216 KB Output is correct
4 Correct 17 ms 80216 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80220 KB Output is correct
7 Correct 17 ms 80220 KB Output is correct
8 Correct 18 ms 80344 KB Output is correct
9 Correct 17 ms 80220 KB Output is correct
10 Correct 19 ms 80336 KB Output is correct
11 Correct 20 ms 80220 KB Output is correct
12 Correct 18 ms 80356 KB Output is correct
13 Correct 17 ms 80220 KB Output is correct
14 Correct 17 ms 80304 KB Output is correct
15 Correct 17 ms 80188 KB Output is correct
16 Correct 18 ms 80472 KB Output is correct
17 Correct 18 ms 80220 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 18 ms 80220 KB Output is correct
20 Correct 18 ms 80220 KB Output is correct
21 Correct 17 ms 80388 KB Output is correct
22 Correct 17 ms 80312 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 18 ms 80220 KB Output is correct
25 Correct 18 ms 80388 KB Output is correct
26 Correct 21 ms 80216 KB Output is correct
27 Correct 17 ms 80220 KB Output is correct
28 Incorrect 18 ms 80220 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 80096 KB Output is correct
2 Correct 17 ms 80084 KB Output is correct
3 Correct 19 ms 80216 KB Output is correct
4 Correct 17 ms 80216 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80220 KB Output is correct
7 Correct 17 ms 80220 KB Output is correct
8 Correct 18 ms 80344 KB Output is correct
9 Correct 17 ms 80220 KB Output is correct
10 Correct 19 ms 80336 KB Output is correct
11 Correct 20 ms 80220 KB Output is correct
12 Correct 18 ms 80356 KB Output is correct
13 Correct 17 ms 80220 KB Output is correct
14 Correct 17 ms 80304 KB Output is correct
15 Correct 17 ms 80188 KB Output is correct
16 Correct 18 ms 80472 KB Output is correct
17 Correct 18 ms 80220 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 18 ms 80220 KB Output is correct
20 Correct 18 ms 80220 KB Output is correct
21 Correct 17 ms 80388 KB Output is correct
22 Correct 17 ms 80312 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 18 ms 80220 KB Output is correct
25 Correct 18 ms 80388 KB Output is correct
26 Correct 21 ms 80216 KB Output is correct
27 Correct 17 ms 80220 KB Output is correct
28 Incorrect 18 ms 80220 KB Output isn't correct
29 Halted 0 ms 0 KB -