oj.uz

Submission #966869

# Submission time Handle Problem Language Result Execution time Memory
966869 2024-04-20T14:00:32 Z Soumya1 New Home (APIO18_new_home) C++17
100 / 100
 2005 ms 180700 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 5;
multiset<int> pos[mxN], ss[4 * mxN];
int t[4 * mxN];
vector<int> comp;
int N;
void update(int x, int lx, int rx, int i, int v) {
  if (lx == rx) {
    if (v > 0) ss[x].insert(v);
    else ss[x].erase(ss[x].find(-v));
    t[x] = (ss[x].empty() ? 0 : *prev(ss[x].end()));
    return;
  }
  int mx = (lx + rx) >> 1;
  if (i <= mx) update(x << 1, lx, mx, i, v);
  else update(x << 1 | 1, mx + 1, rx, i, v);
  t[x] = max(t[x << 1], t[x << 1 | 1]);
}
void insert(int l, int r) {
  l = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
  r = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
  update(1, 1, N, l, r);
}
void erase(int l, int r) {
  l = lower_bound(comp.begin(), comp.end(), l) - comp.begin();
  r = lower_bound(comp.begin(), comp.end(), r) - comp.begin();
  update(1, 1, N, l, -r);
}
int get(int x, int lx, int rx, int l, int r) {
  if (l > rx || lx > r) return -1e9;
  if (l <= lx && r >= rx) return t[x];
  int mx = (lx + rx) >> 1;
  return max(get(x << 1, lx, mx, l, r), get(x << 1 | 1, mx + 1, rx, l, r));
}
int query(int x, int lx, int rx, int y, int r = -1e9) {
  if (lx == rx) return lx;
  int mx = (lx + rx) >> 1;
  if (comp[mx] >= y) return query(x << 1, lx, mx, y);
  if (y - comp[mx] - 1 >= max(comp[t[x << 1]], r) - y) return query(x << 1 | 1, mx + 1, rx, y, max(r, comp[t[x << 1]]));
  return query(x << 1, lx, mx, y, r);
}
void testCase() {
  int n, q, k;
  cin >> n >> k >> q;
  vector<array<int, 4>> all;
  comp = {(int) 4e8, (int) -4e8};
  for (int i = 0; i < n; i++) {
    int x, t, a, b;
    cin >> x >> t >> a >> b;
    all.push_back({a, 2, t, x});
    all.push_back({b + 1, 1, t, x});
    comp.push_back(x);
  }
  vector<int> ans(q);
  for (int i = 0; i < q; i++) {
    int l, y;
    cin >> l >> y;
    all.push_back({y, 3, i, l});
  }
  sort(all.begin(), all.end());
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  N = comp.size();
  comp.insert(comp.begin(), -1e9);
  for (int i = 1; i <= k; i++) {
    pos[i].insert((int) -4e8);
    pos[i].insert(4e8);
    insert(-4e8, 4e8);
  }
  for (auto v : all) {
    if (v[1] == 1) {
      auto b = pos[v[2]].upper_bound(v[3]);
      auto s = prev(prev(b));
      erase(*s, v[3]);
      erase(v[3], *b);
      insert(*s, *b);
      pos[v[2]].erase(pos[v[2]].find(v[3]));
    } else if (v[1] == 2) {
      auto b = pos[v[2]].upper_bound(v[3]);
      auto s = prev(b);
      erase(*s, *b);
      pos[v[2]].insert(v[3]);
      insert(*s, v[3]);
      insert(v[3], *b);
    } else {
      if (get(1, 1, N, 1, 1) == N) {
        ans[v[2]] = -1;
        continue;
      }
      int x = query(1, 1, N, v[3]);
      int r = comp[get(1, 1, N, 1, x - 1)];
      int R = r - v[3];
      int L = v[3] - comp[x];
      ans[v[2]] = max(L, R);
    }
  }
  for (int i : ans) cout << i << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 71256 KB Output is correct
2 Correct 15 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Correct 15 ms 71260 KB Output is correct
5 Correct 16 ms 71260 KB Output is correct
6 Correct 16 ms 71260 KB Output is correct
7 Correct 16 ms 71256 KB Output is correct
8 Correct 16 ms 71388 KB Output is correct
9 Correct 16 ms 71256 KB Output is correct
10 Correct 17 ms 71236 KB Output is correct
11 Correct 16 ms 71256 KB Output is correct
12 Correct 16 ms 71260 KB Output is correct
13 Correct 16 ms 71260 KB Output is correct
14 Correct 16 ms 71260 KB Output is correct
15 Correct 16 ms 71260 KB Output is correct
16 Correct 16 ms 71260 KB Output is correct
17 Correct 18 ms 71344 KB Output is correct
18 Correct 16 ms 71260 KB Output is correct
19 Correct 16 ms 71260 KB Output is correct
20 Correct 16 ms 71260 KB Output is correct
21 Correct 16 ms 71256 KB Output is correct
22 Correct 16 ms 71276 KB Output is correct
23 Correct 15 ms 71260 KB Output is correct
24 Correct 16 ms 71260 KB Output is correct
25 Correct 16 ms 71288 KB Output is correct
26 Correct 16 ms 71260 KB Output is correct
27 Correct 16 ms 71516 KB Output is correct
28 Correct 16 ms 71292 KB Output is correct
29 Correct 16 ms 71456 KB Output is correct
30 Correct 16 ms 71260 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 71256 KB Output is correct
2 Correct 15 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Correct 15 ms 71260 KB Output is correct
5 Correct 16 ms 71260 KB Output is correct
6 Correct 16 ms 71260 KB Output is correct
7 Correct 16 ms 71256 KB Output is correct
8 Correct 16 ms 71388 KB Output is correct
9 Correct 16 ms 71256 KB Output is correct
10 Correct 17 ms 71236 KB Output is correct
11 Correct 16 ms 71256 KB Output is correct
12 Correct 16 ms 71260 KB Output is correct
13 Correct 16 ms 71260 KB Output is correct
14 Correct 16 ms 71260 KB Output is correct
15 Correct 16 ms 71260 KB Output is correct
16 Correct 16 ms 71260 KB Output is correct
17 Correct 18 ms 71344 KB Output is correct
18 Correct 16 ms 71260 KB Output is correct
19 Correct 16 ms 71260 KB Output is correct
20 Correct 16 ms 71260 KB Output is correct
21 Correct 16 ms 71256 KB Output is correct
22 Correct 16 ms 71276 KB Output is correct
23 Correct 15 ms 71260 KB Output is correct
24 Correct 16 ms 71260 KB Output is correct
25 Correct 16 ms 71288 KB Output is correct
26 Correct 16 ms 71260 KB Output is correct
27 Correct 16 ms 71516 KB Output is correct
28 Correct 16 ms 71292 KB Output is correct
29 Correct 16 ms 71456 KB Output is correct
30 Correct 16 ms 71260 KB Output is correct
31 Correct 245 ms 85780 KB Output is correct
32 Correct 109 ms 77908 KB Output is correct
33 Correct 241 ms 82040 KB Output is correct
34 Correct 229 ms 82324 KB Output is correct
35 Correct 256 ms 85660 KB Output is correct
36 Correct 241 ms 85484 KB Output is correct
37 Correct 204 ms 80888 KB Output is correct
38 Correct 211 ms 80568 KB Output is correct
39 Correct 181 ms 80456 KB Output is correct
40 Correct 185 ms 80012 KB Output is correct
41 Correct 195 ms 80528 KB Output is correct
42 Correct 190 ms 80500 KB Output is correct
43 Correct 107 ms 83576 KB Output is correct
44 Correct 212 ms 80308 KB Output is correct
45 Correct 190 ms 80100 KB Output is correct
46 Correct 179 ms 80116 KB Output is correct
47 Correct 147 ms 79864 KB Output is correct
48 Correct 140 ms 80052 KB Output is correct
49 Correct 154 ms 79832 KB Output is correct
50 Correct 170 ms 81044 KB Output is correct
51 Correct 157 ms 80120 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1212 ms 132848 KB Output is correct
2 Correct 969 ms 123436 KB Output is correct
3 Correct 1501 ms 167448 KB Output is correct
4 Correct 1346 ms 137292 KB Output is correct
5 Correct 899 ms 121972 KB Output is correct
6 Correct 939 ms 121952 KB Output is correct
7 Correct 1563 ms 167140 KB Output is correct
8 Correct 1309 ms 137604 KB Output is correct
9 Correct 1210 ms 129040 KB Output is correct
10 Correct 988 ms 125284 KB Output is correct
11 Correct 860 ms 122388 KB Output is correct
12 Correct 918 ms 123080 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1444 ms 123472 KB Output is correct
2 Correct 549 ms 121420 KB Output is correct
3 Correct 1451 ms 134360 KB Output is correct
4 Correct 1811 ms 178124 KB Output is correct
5 Correct 1612 ms 144656 KB Output is correct
6 Correct 1718 ms 148944 KB Output is correct
7 Correct 1510 ms 134428 KB Output is correct
8 Correct 1534 ms 134240 KB Output is correct
9 Correct 1851 ms 179596 KB Output is correct
10 Correct 1619 ms 147904 KB Output is correct
11 Correct 1547 ms 139120 KB Output is correct
12 Correct 1476 ms 135956 KB Output is correct
13 Correct 892 ms 133544 KB Output is correct
14 Correct 881 ms 132740 KB Output is correct
15 Correct 976 ms 134760 KB Output is correct
16 Correct 1043 ms 136628 KB Output is correct
17 Correct 1010 ms 133636 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 71256 KB Output is correct
2 Correct 15 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Correct 15 ms 71260 KB Output is correct
5 Correct 16 ms 71260 KB Output is correct
6 Correct 16 ms 71260 KB Output is correct
7 Correct 16 ms 71256 KB Output is correct
8 Correct 16 ms 71388 KB Output is correct
9 Correct 16 ms 71256 KB Output is correct
10 Correct 17 ms 71236 KB Output is correct
11 Correct 16 ms 71256 KB Output is correct
12 Correct 16 ms 71260 KB Output is correct
13 Correct 16 ms 71260 KB Output is correct
14 Correct 16 ms 71260 KB Output is correct
15 Correct 16 ms 71260 KB Output is correct
16 Correct 16 ms 71260 KB Output is correct
17 Correct 18 ms 71344 KB Output is correct
18 Correct 16 ms 71260 KB Output is correct
19 Correct 16 ms 71260 KB Output is correct
20 Correct 16 ms 71260 KB Output is correct
21 Correct 16 ms 71256 KB Output is correct
22 Correct 16 ms 71276 KB Output is correct
23 Correct 15 ms 71260 KB Output is correct
24 Correct 16 ms 71260 KB Output is correct
25 Correct 16 ms 71288 KB Output is correct
26 Correct 16 ms 71260 KB Output is correct
27 Correct 16 ms 71516 KB Output is correct
28 Correct 16 ms 71292 KB Output is correct
29 Correct 16 ms 71456 KB Output is correct
30 Correct 16 ms 71260 KB Output is correct
31 Correct 245 ms 85780 KB Output is correct
32 Correct 109 ms 77908 KB Output is correct
33 Correct 241 ms 82040 KB Output is correct
34 Correct 229 ms 82324 KB Output is correct
35 Correct 256 ms 85660 KB Output is correct
36 Correct 241 ms 85484 KB Output is correct
37 Correct 204 ms 80888 KB Output is correct
38 Correct 211 ms 80568 KB Output is correct
39 Correct 181 ms 80456 KB Output is correct
40 Correct 185 ms 80012 KB Output is correct
41 Correct 195 ms 80528 KB Output is correct
42 Correct 190 ms 80500 KB Output is correct
43 Correct 107 ms 83576 KB Output is correct
44 Correct 212 ms 80308 KB Output is correct
45 Correct 190 ms 80100 KB Output is correct
46 Correct 179 ms 80116 KB Output is correct
47 Correct 147 ms 79864 KB Output is correct
48 Correct 140 ms 80052 KB Output is correct
49 Correct 154 ms 79832 KB Output is correct
50 Correct 170 ms 81044 KB Output is correct
51 Correct 157 ms 80120 KB Output is correct
52 Correct 258 ms 93948 KB Output is correct
53 Correct 243 ms 90536 KB Output is correct
54 Correct 262 ms 88344 KB Output is correct
55 Correct 207 ms 85096 KB Output is correct
56 Correct 231 ms 87464 KB Output is correct
57 Correct 204 ms 82528 KB Output is correct
58 Correct 224 ms 84988 KB Output is correct
59 Correct 218 ms 88572 KB Output is correct
60 Correct 203 ms 81640 KB Output is correct
61 Correct 125 ms 92084 KB Output is correct
62 Correct 264 ms 94080 KB Output is correct
63 Correct 259 ms 89056 KB Output is correct
64 Correct 217 ms 86776 KB Output is correct
65 Correct 222 ms 82420 KB Output is correct
66 Correct 200 ms 80376 KB Output is correct
67 Correct 155 ms 78624 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 71256 KB Output is correct
2 Correct 15 ms 71260 KB Output is correct
3 Correct 15 ms 71260 KB Output is correct
4 Correct 15 ms 71260 KB Output is correct
5 Correct 16 ms 71260 KB Output is correct
6 Correct 16 ms 71260 KB Output is correct
7 Correct 16 ms 71256 KB Output is correct
8 Correct 16 ms 71388 KB Output is correct
9 Correct 16 ms 71256 KB Output is correct
10 Correct 17 ms 71236 KB Output is correct
11 Correct 16 ms 71256 KB Output is correct
12 Correct 16 ms 71260 KB Output is correct
13 Correct 16 ms 71260 KB Output is correct
14 Correct 16 ms 71260 KB Output is correct
15 Correct 16 ms 71260 KB Output is correct
16 Correct 16 ms 71260 KB Output is correct
17 Correct 18 ms 71344 KB Output is correct
18 Correct 16 ms 71260 KB Output is correct
19 Correct 16 ms 71260 KB Output is correct
20 Correct 16 ms 71260 KB Output is correct
21 Correct 16 ms 71256 KB Output is correct
22 Correct 16 ms 71276 KB Output is correct
23 Correct 15 ms 71260 KB Output is correct
24 Correct 16 ms 71260 KB Output is correct
25 Correct 16 ms 71288 KB Output is correct
26 Correct 16 ms 71260 KB Output is correct
27 Correct 16 ms 71516 KB Output is correct
28 Correct 16 ms 71292 KB Output is correct
29 Correct 16 ms 71456 KB Output is correct
30 Correct 16 ms 71260 KB Output is correct
31 Correct 245 ms 85780 KB Output is correct
32 Correct 109 ms 77908 KB Output is correct
33 Correct 241 ms 82040 KB Output is correct
34 Correct 229 ms 82324 KB Output is correct
35 Correct 256 ms 85660 KB Output is correct
36 Correct 241 ms 85484 KB Output is correct
37 Correct 204 ms 80888 KB Output is correct
38 Correct 211 ms 80568 KB Output is correct
39 Correct 181 ms 80456 KB Output is correct
40 Correct 185 ms 80012 KB Output is correct
41 Correct 195 ms 80528 KB Output is correct
42 Correct 190 ms 80500 KB Output is correct
43 Correct 107 ms 83576 KB Output is correct
44 Correct 212 ms 80308 KB Output is correct
45 Correct 190 ms 80100 KB Output is correct
46 Correct 179 ms 80116 KB Output is correct
47 Correct 147 ms 79864 KB Output is correct
48 Correct 140 ms 80052 KB Output is correct
49 Correct 154 ms 79832 KB Output is correct
50 Correct 170 ms 81044 KB Output is correct
51 Correct 157 ms 80120 KB Output is correct
52 Correct 1212 ms 132848 KB Output is correct
53 Correct 969 ms 123436 KB Output is correct
54 Correct 1501 ms 167448 KB Output is correct
55 Correct 1346 ms 137292 KB Output is correct
56 Correct 899 ms 121972 KB Output is correct
57 Correct 939 ms 121952 KB Output is correct
58 Correct 1563 ms 167140 KB Output is correct
59 Correct 1309 ms 137604 KB Output is correct
60 Correct 1210 ms 129040 KB Output is correct
61 Correct 988 ms 125284 KB Output is correct
62 Correct 860 ms 122388 KB Output is correct
63 Correct 918 ms 123080 KB Output is correct
64 Correct 1444 ms 123472 KB Output is correct
65 Correct 549 ms 121420 KB Output is correct
66 Correct 1451 ms 134360 KB Output is correct
67 Correct 1811 ms 178124 KB Output is correct
68 Correct 1612 ms 144656 KB Output is correct
69 Correct 1718 ms 148944 KB Output is correct
70 Correct 1510 ms 134428 KB Output is correct
71 Correct 1534 ms 134240 KB Output is correct
72 Correct 1851 ms 179596 KB Output is correct
73 Correct 1619 ms 147904 KB Output is correct
74 Correct 1547 ms 139120 KB Output is correct
75 Correct 1476 ms 135956 KB Output is correct
76 Correct 892 ms 133544 KB Output is correct
77 Correct 881 ms 132740 KB Output is correct
78 Correct 976 ms 134760 KB Output is correct
79 Correct 1043 ms 136628 KB Output is correct
80 Correct 1010 ms 133636 KB Output is correct
81 Correct 258 ms 93948 KB Output is correct
82 Correct 243 ms 90536 KB Output is correct
83 Correct 262 ms 88344 KB Output is correct
84 Correct 207 ms 85096 KB Output is correct
85 Correct 231 ms 87464 KB Output is correct
86 Correct 204 ms 82528 KB Output is correct
87 Correct 224 ms 84988 KB Output is correct
88 Correct 218 ms 88572 KB Output is correct
89 Correct 203 ms 81640 KB Output is correct
90 Correct 125 ms 92084 KB Output is correct
91 Correct 264 ms 94080 KB Output is correct
92 Correct 259 ms 89056 KB Output is correct
93 Correct 217 ms 86776 KB Output is correct
94 Correct 222 ms 82420 KB Output is correct
95 Correct 200 ms 80376 KB Output is correct
96 Correct 155 ms 78624 KB Output is correct
97 Correct 1978 ms 179540 KB Output is correct
98 Correct 519 ms 104684 KB Output is correct
99 Correct 1563 ms 118872 KB Output is correct
100 Correct 1862 ms 161200 KB Output is correct
101 Correct 2005 ms 151680 KB Output is correct
102 Correct 1946 ms 136232 KB Output is correct
103 Correct 1244 ms 110456 KB Output is correct
104 Correct 1289 ms 111112 KB Output is correct
105 Correct 1032 ms 110488 KB Output is correct
106 Correct 1054 ms 110268 KB Output is correct
107 Correct 1333 ms 134864 KB Output is correct
108 Correct 1482 ms 145620 KB Output is correct
109 Correct 1158 ms 117860 KB Output is correct
110 Correct 1357 ms 133740 KB Output is correct
111 Correct 1431 ms 146124 KB Output is correct
112 Correct 1193 ms 117300 KB Output is correct
113 Correct 690 ms 174880 KB Output is correct
114 Correct 1924 ms 180700 KB Output is correct
115 Correct 1978 ms 154828 KB Output is correct
116 Correct 1864 ms 142168 KB Output is correct
117 Correct 1538 ms 121100 KB Output is correct
118 Correct 1175 ms 111468 KB Output is correct
119 Correct 950 ms 107016 KB Output is correct
120 Correct 660 ms 109108 KB Output is correct
121 Correct 740 ms 109060 KB Output is correct
122 Correct 748 ms 108780 KB Output is correct
123 Correct 785 ms 110076 KB Output is correct
124 Correct 871 ms 111028 KB Output is correct
125 Correct 830 ms 109984 KB Output is correct
126 Correct 900 ms 110308 KB Output is correct