oj.uz

Submission #937482

# Submission time Handle Problem Language Result Execution time Memory
937482 2024-03-04T06:48:56 Z rxlfd314 New Home (APIO18_new_home) C++17
100 / 100
 2701 ms 153740 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) {
    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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 80216 KB Output is correct
2 Correct 19 ms 80216 KB Output is correct
3 Correct 16 ms 80220 KB Output is correct
4 Correct 18 ms 80076 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80320 KB Output is correct
7 Correct 18 ms 80216 KB Output is correct
8 Correct 21 ms 80220 KB Output is correct
9 Correct 19 ms 80220 KB Output is correct
10 Correct 20 ms 80220 KB Output is correct
11 Correct 17 ms 80216 KB Output is correct
12 Correct 22 ms 80348 KB Output is correct
13 Correct 18 ms 80220 KB Output is correct
14 Correct 19 ms 80120 KB Output is correct
15 Correct 18 ms 80220 KB Output is correct
16 Correct 18 ms 80216 KB Output is correct
17 Correct 22 ms 80372 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 17 ms 80348 KB Output is correct
20 Correct 18 ms 80216 KB Output is correct
21 Correct 17 ms 80220 KB Output is correct
22 Correct 19 ms 80196 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 20 ms 80388 KB Output is correct
25 Correct 19 ms 80220 KB Output is correct
26 Correct 18 ms 80220 KB Output is correct
27 Correct 19 ms 80220 KB Output is correct
28 Correct 18 ms 80340 KB Output is correct
29 Correct 20 ms 80220 KB Output is correct
30 Correct 20 ms 80340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 80216 KB Output is correct
2 Correct 19 ms 80216 KB Output is correct
3 Correct 16 ms 80220 KB Output is correct
4 Correct 18 ms 80076 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80320 KB Output is correct
7 Correct 18 ms 80216 KB Output is correct
8 Correct 21 ms 80220 KB Output is correct
9 Correct 19 ms 80220 KB Output is correct
10 Correct 20 ms 80220 KB Output is correct
11 Correct 17 ms 80216 KB Output is correct
12 Correct 22 ms 80348 KB Output is correct
13 Correct 18 ms 80220 KB Output is correct
14 Correct 19 ms 80120 KB Output is correct
15 Correct 18 ms 80220 KB Output is correct
16 Correct 18 ms 80216 KB Output is correct
17 Correct 22 ms 80372 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 17 ms 80348 KB Output is correct
20 Correct 18 ms 80216 KB Output is correct
21 Correct 17 ms 80220 KB Output is correct
22 Correct 19 ms 80196 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 20 ms 80388 KB Output is correct
25 Correct 19 ms 80220 KB Output is correct
26 Correct 18 ms 80220 KB Output is correct
27 Correct 19 ms 80220 KB Output is correct
28 Correct 18 ms 80340 KB Output is correct
29 Correct 20 ms 80220 KB Output is correct
30 Correct 20 ms 80340 KB Output is correct
31 Correct 348 ms 94380 KB Output is correct
32 Correct 69 ms 84996 KB Output is correct
33 Correct 300 ms 92824 KB Output is correct
34 Correct 319 ms 93824 KB Output is correct
35 Correct 319 ms 95224 KB Output is correct
36 Correct 362 ms 94660 KB Output is correct
37 Correct 253 ms 92644 KB Output is correct
38 Correct 251 ms 93120 KB Output is correct
39 Correct 205 ms 92096 KB Output is correct
40 Correct 216 ms 92184 KB Output is correct
41 Correct 232 ms 92884 KB Output is correct
42 Correct 219 ms 92808 KB Output is correct
43 Correct 73 ms 86476 KB Output is correct
44 Correct 253 ms 91580 KB Output is correct
45 Correct 221 ms 91576 KB Output is correct
46 Correct 215 ms 91068 KB Output is correct
47 Correct 146 ms 89660 KB Output is correct
48 Correct 143 ms 90556 KB Output is correct
49 Correct 165 ms 90548 KB Output is correct
50 Correct 182 ms 90808 KB Output is correct
51 Correct 175 ms 91584 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1251 ms 134960 KB Output is correct
2 Correct 862 ms 129964 KB Output is correct
3 Correct 629 ms 132240 KB Output is correct
4 Correct 1173 ms 137116 KB Output is correct
5 Correct 727 ms 119444 KB Output is correct
6 Correct 883 ms 141508 KB Output is correct
7 Correct 629 ms 147116 KB Output is correct
8 Correct 1193 ms 148176 KB Output is correct
9 Correct 1301 ms 147280 KB Output is correct
10 Correct 1033 ms 143388 KB Output is correct
11 Correct 874 ms 141116 KB Output is correct
12 Correct 959 ms 145088 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1963 ms 132524 KB Output is correct
2 Correct 263 ms 100092 KB Output is correct
3 Correct 1792 ms 130408 KB Output is correct
4 Correct 694 ms 135852 KB Output is correct
5 Correct 1574 ms 133788 KB Output is correct
6 Correct 1373 ms 134828 KB Output is correct
7 Correct 1391 ms 124168 KB Output is correct
8 Correct 1732 ms 140736 KB Output is correct
9 Correct 762 ms 152188 KB Output is correct
10 Correct 1575 ms 148572 KB Output is correct
11 Correct 2020 ms 147592 KB Output is correct
12 Correct 2082 ms 143656 KB Output is correct
13 Correct 912 ms 139356 KB Output is correct
14 Correct 902 ms 137440 KB Output is correct
15 Correct 1069 ms 139328 KB Output is correct
16 Correct 1200 ms 143276 KB Output is correct
17 Correct 1069 ms 140916 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 80216 KB Output is correct
2 Correct 19 ms 80216 KB Output is correct
3 Correct 16 ms 80220 KB Output is correct
4 Correct 18 ms 80076 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80320 KB Output is correct
7 Correct 18 ms 80216 KB Output is correct
8 Correct 21 ms 80220 KB Output is correct
9 Correct 19 ms 80220 KB Output is correct
10 Correct 20 ms 80220 KB Output is correct
11 Correct 17 ms 80216 KB Output is correct
12 Correct 22 ms 80348 KB Output is correct
13 Correct 18 ms 80220 KB Output is correct
14 Correct 19 ms 80120 KB Output is correct
15 Correct 18 ms 80220 KB Output is correct
16 Correct 18 ms 80216 KB Output is correct
17 Correct 22 ms 80372 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 17 ms 80348 KB Output is correct
20 Correct 18 ms 80216 KB Output is correct
21 Correct 17 ms 80220 KB Output is correct
22 Correct 19 ms 80196 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 20 ms 80388 KB Output is correct
25 Correct 19 ms 80220 KB Output is correct
26 Correct 18 ms 80220 KB Output is correct
27 Correct 19 ms 80220 KB Output is correct
28 Correct 18 ms 80340 KB Output is correct
29 Correct 20 ms 80220 KB Output is correct
30 Correct 20 ms 80340 KB Output is correct
31 Correct 348 ms 94380 KB Output is correct
32 Correct 69 ms 84996 KB Output is correct
33 Correct 300 ms 92824 KB Output is correct
34 Correct 319 ms 93824 KB Output is correct
35 Correct 319 ms 95224 KB Output is correct
36 Correct 362 ms 94660 KB Output is correct
37 Correct 253 ms 92644 KB Output is correct
38 Correct 251 ms 93120 KB Output is correct
39 Correct 205 ms 92096 KB Output is correct
40 Correct 216 ms 92184 KB Output is correct
41 Correct 232 ms 92884 KB Output is correct
42 Correct 219 ms 92808 KB Output is correct
43 Correct 73 ms 86476 KB Output is correct
44 Correct 253 ms 91580 KB Output is correct
45 Correct 221 ms 91576 KB Output is correct
46 Correct 215 ms 91068 KB Output is correct
47 Correct 146 ms 89660 KB Output is correct
48 Correct 143 ms 90556 KB Output is correct
49 Correct 165 ms 90548 KB Output is correct
50 Correct 182 ms 90808 KB Output is correct
51 Correct 175 ms 91584 KB Output is correct
52 Correct 139 ms 94400 KB Output is correct
53 Correct 141 ms 92204 KB Output is correct
54 Correct 215 ms 94140 KB Output is correct
55 Correct 202 ms 93588 KB Output is correct
56 Correct 195 ms 93872 KB Output is correct
57 Correct 228 ms 92072 KB Output is correct
58 Correct 202 ms 92952 KB Output is correct
59 Correct 184 ms 94012 KB Output is correct
60 Correct 214 ms 91828 KB Output is correct
61 Correct 72 ms 93412 KB Output is correct
62 Correct 147 ms 95168 KB Output is correct
63 Correct 189 ms 93840 KB Output is correct
64 Correct 201 ms 93848 KB Output is correct
65 Correct 233 ms 92352 KB Output is correct
66 Correct 222 ms 91584 KB Output is correct
67 Correct 137 ms 89788 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 80216 KB Output is correct
2 Correct 19 ms 80216 KB Output is correct
3 Correct 16 ms 80220 KB Output is correct
4 Correct 18 ms 80076 KB Output is correct
5 Correct 17 ms 80220 KB Output is correct
6 Correct 17 ms 80320 KB Output is correct
7 Correct 18 ms 80216 KB Output is correct
8 Correct 21 ms 80220 KB Output is correct
9 Correct 19 ms 80220 KB Output is correct
10 Correct 20 ms 80220 KB Output is correct
11 Correct 17 ms 80216 KB Output is correct
12 Correct 22 ms 80348 KB Output is correct
13 Correct 18 ms 80220 KB Output is correct
14 Correct 19 ms 80120 KB Output is correct
15 Correct 18 ms 80220 KB Output is correct
16 Correct 18 ms 80216 KB Output is correct
17 Correct 22 ms 80372 KB Output is correct
18 Correct 18 ms 80220 KB Output is correct
19 Correct 17 ms 80348 KB Output is correct
20 Correct 18 ms 80216 KB Output is correct
21 Correct 17 ms 80220 KB Output is correct
22 Correct 19 ms 80196 KB Output is correct
23 Correct 18 ms 80220 KB Output is correct
24 Correct 20 ms 80388 KB Output is correct
25 Correct 19 ms 80220 KB Output is correct
26 Correct 18 ms 80220 KB Output is correct
27 Correct 19 ms 80220 KB Output is correct
28 Correct 18 ms 80340 KB Output is correct
29 Correct 20 ms 80220 KB Output is correct
30 Correct 20 ms 80340 KB Output is correct
31 Correct 348 ms 94380 KB Output is correct
32 Correct 69 ms 84996 KB Output is correct
33 Correct 300 ms 92824 KB Output is correct
34 Correct 319 ms 93824 KB Output is correct
35 Correct 319 ms 95224 KB Output is correct
36 Correct 362 ms 94660 KB Output is correct
37 Correct 253 ms 92644 KB Output is correct
38 Correct 251 ms 93120 KB Output is correct
39 Correct 205 ms 92096 KB Output is correct
40 Correct 216 ms 92184 KB Output is correct
41 Correct 232 ms 92884 KB Output is correct
42 Correct 219 ms 92808 KB Output is correct
43 Correct 73 ms 86476 KB Output is correct
44 Correct 253 ms 91580 KB Output is correct
45 Correct 221 ms 91576 KB Output is correct
46 Correct 215 ms 91068 KB Output is correct
47 Correct 146 ms 89660 KB Output is correct
48 Correct 143 ms 90556 KB Output is correct
49 Correct 165 ms 90548 KB Output is correct
50 Correct 182 ms 90808 KB Output is correct
51 Correct 175 ms 91584 KB Output is correct
52 Correct 1251 ms 134960 KB Output is correct
53 Correct 862 ms 129964 KB Output is correct
54 Correct 629 ms 132240 KB Output is correct
55 Correct 1173 ms 137116 KB Output is correct
56 Correct 727 ms 119444 KB Output is correct
57 Correct 883 ms 141508 KB Output is correct
58 Correct 629 ms 147116 KB Output is correct
59 Correct 1193 ms 148176 KB Output is correct
60 Correct 1301 ms 147280 KB Output is correct
61 Correct 1033 ms 143388 KB Output is correct
62 Correct 874 ms 141116 KB Output is correct
63 Correct 959 ms 145088 KB Output is correct
64 Correct 1963 ms 132524 KB Output is correct
65 Correct 263 ms 100092 KB Output is correct
66 Correct 1792 ms 130408 KB Output is correct
67 Correct 694 ms 135852 KB Output is correct
68 Correct 1574 ms 133788 KB Output is correct
69 Correct 1373 ms 134828 KB Output is correct
70 Correct 1391 ms 124168 KB Output is correct
71 Correct 1732 ms 140736 KB Output is correct
72 Correct 762 ms 152188 KB Output is correct
73 Correct 1575 ms 148572 KB Output is correct
74 Correct 2020 ms 147592 KB Output is correct
75 Correct 2082 ms 143656 KB Output is correct
76 Correct 912 ms 139356 KB Output is correct
77 Correct 902 ms 137440 KB Output is correct
78 Correct 1069 ms 139328 KB Output is correct
79 Correct 1200 ms 143276 KB Output is correct
80 Correct 1069 ms 140916 KB Output is correct
81 Correct 139 ms 94400 KB Output is correct
82 Correct 141 ms 92204 KB Output is correct
83 Correct 215 ms 94140 KB Output is correct
84 Correct 202 ms 93588 KB Output is correct
85 Correct 195 ms 93872 KB Output is correct
86 Correct 228 ms 92072 KB Output is correct
87 Correct 202 ms 92952 KB Output is correct
88 Correct 184 ms 94012 KB Output is correct
89 Correct 214 ms 91828 KB Output is correct
90 Correct 72 ms 93412 KB Output is correct
91 Correct 147 ms 95168 KB Output is correct
92 Correct 189 ms 93840 KB Output is correct
93 Correct 201 ms 93848 KB Output is correct
94 Correct 233 ms 92352 KB Output is correct
95 Correct 222 ms 91584 KB Output is correct
96 Correct 137 ms 89788 KB Output is correct
97 Correct 797 ms 153212 KB Output is correct
98 Correct 276 ms 104108 KB Output is correct
99 Correct 2569 ms 144200 KB Output is correct
100 Correct 767 ms 142768 KB Output is correct
101 Correct 1581 ms 149496 KB Output is correct
102 Correct 2701 ms 150808 KB Output is correct
103 Correct 1560 ms 142840 KB Output is correct
104 Correct 1523 ms 142584 KB Output is correct
105 Correct 1191 ms 141792 KB Output is correct
106 Correct 1218 ms 142756 KB Output is correct
107 Correct 1242 ms 146124 KB Output is correct
108 Correct 1157 ms 152508 KB Output is correct
109 Correct 1370 ms 142256 KB Output is correct
110 Correct 1245 ms 143880 KB Output is correct
111 Correct 1160 ms 150204 KB Output is correct
112 Correct 1370 ms 140088 KB Output is correct
113 Correct 292 ms 142940 KB Output is correct
114 Correct 832 ms 153740 KB Output is correct
115 Correct 1318 ms 152740 KB Output is correct
116 Correct 1486 ms 149268 KB Output is correct
117 Correct 1633 ms 141600 KB Output is correct
118 Correct 1550 ms 138340 KB Output is correct
119 Correct 653 ms 123120 KB Output is correct
120 Correct 612 ms 126060 KB Output is correct
121 Correct 769 ms 131536 KB Output is correct
122 Correct 755 ms 131260 KB Output is correct
123 Correct 875 ms 133148 KB Output is correct
124 Correct 939 ms 134240 KB Output is correct
125 Correct 918 ms 132340 KB Output is correct
126 Correct 925 ms 133644 KB Output is correct