oj.uz

Submission #1029608

# Submission time Handle Problem Language Result Execution time Memory
1029608 2024-07-21T05:44:27 Z erray New Home (APIO18_new_home) C++17
100 / 100
 4642 ms 630628 KB 
// author: erray
#include <bits/stdc++.h>
 
#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif
 
using namespace std;
 
vector<multiset<int>> mss;
constexpr int NODES = int(3e7);

constexpr int inf = int(3e8);
struct node {
  int L, R;
  int mx;
  int multiset_id;
  void add(int x) {
    if (multiset_id == -1) {
      multiset_id = int(mss.size());
      mss.emplace_back();
    }
    mss[multiset_id].insert(x);
    mx = *mss[multiset_id].rbegin();
  }
  void rem(int x) {
    mss[multiset_id].erase(mss[multiset_id].find(x));
    mx = (mss[multiset_id].empty() ? -inf : *mss[multiset_id].rbegin());
  }
  void init() {
    L = 0, R = 0;
    mx = -inf;
    multiset_id = -1;
  }
};

node nodes[NODES];
int last_node = 1;

void pull(node& x) {
  x.mx = max(nodes[x.L].mx, nodes[x.R].mx);
}
void branch(node& x) {
  if (x.L == 0) {
    nodes[last_node].init();
    x.L = last_node++;
  } 
  if (x.R == 0) {
    nodes[last_node].init();
    x.R = last_node++;
  } 
}
 
struct SegTree {
  void modify(int v, int l, int r, int p, int x, int t) {
    if (l == r) {
      if (t) {
        nodes[v].add(x);
      } else {
        nodes[v].rem(x);
      }
      return;
    }
    branch(nodes[v]);
    int mid = (l + r) >> 1;
    if (p <= mid) {
      modify(nodes[v].L, l, mid, p, x, t);
    } else {
      modify(nodes[v].R, mid + 1, r, p, x, t);
    }
    pull(nodes[v]);
  }
  int get(int v, int l, int r, int ll, int rr) {
    if (l >= ll && rr >= r) {
      return nodes[v].mx;
    }
    int mid = (l + r) >> 1;
    int res = -inf;
    if (ll <= mid && nodes[v].R != 0) {
      res = max(res, get(nodes[v].L, l, mid, ll, rr));
    }
    if (mid < rr && nodes[v].R != 0) {
      res = max(res, get(nodes[v].R, mid + 1, r, ll, rr));
    }
    return res;
  }
  int mn, mx;
  int root;
  SegTree(int _mn, int _mx) : mn(_mn), mx(_mx) {
    nodes[last_node].init();
    root = last_node++;
  }
  void modify(int p, int x, int t) {
    modify(root, mn, mx, p, x, t);
  }
  int get(int ll, int rr) {
    return get(root, mn, mx, ll, rr);
  }
};
 
constexpr int POS = int(1e8);
 
int main() {
 
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  nodes[0].init();
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> X(N), T(N), A(N), B(N);
  for (int i = 0; i < N; ++i) {
    cin >> X[i] >> T[i] >> A[i] >> B[i];
    --T[i];
  }
  vector<int> L(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> L[i] >> Y[i];
  }
  vector<array<int, 2>> events;
  for (int i = 0; i < N; ++i) {
    events.push_back({A[i], i});
    events.push_back({B[i] + 1, ~i}); 
  }
  for (int i = 0; i < Q; ++i) {
    events.push_back({Y[i], i + N});
  }
  debug(events);
  sort(events.begin(), events.end());
  SegTree pref(1, POS), suf(1, POS);
  vector<map<int, int>> acts(K);
  auto Updates = [&](int t, int x) -> vector<array<int, 3>> {
    debug(t, x);
    if (acts[t].empty()) {
      return {};
    }
    vector<array<int, 3>> res;
    auto it = acts[t].lower_bound(x);
    vector<array<int, 2>> regulars;
    if (it != acts[t].end() && it->first == x) {
       if (next(it) == acts[t].end()) {
         res.push_back({t, POS, POS - x});
       } else {
         regulars.push_back({it->first, next(it)->first});
       }
       if (it == acts[t].begin()) {
         res.push_back({t, 1, x - 1});
       } else {
         regulars.push_back({prev(it)->first, it->first});
       }
    } else {
      if (it == acts[t].end()) {
        res.push_back({t, POS, POS - prev(it)->first});
      } else if (it == acts[t].begin()) {
        res.push_back({t, 1, it->first - 1});
      } else {
        regulars.push_back({prev(it)->first, it->first});
      }
    }
    for (auto[l, r] : regulars) {
      int dist = (r - l) / 2, mid = (l + r) / 2;
      if ((l + r) % 2 == 1) {
        res.push_back({t, mid, dist});
        res.push_back({t, mid + 1, dist});
      } else {
        res.push_back({t, mid, dist}); 
      }
    }
    return res;
  };
  auto Rem = [&](vector<array<int, 3>> a) {
    for (auto[t, x, v] : a) {
      pref.modify(x, v + x, 0);
      suf.modify(x, v - x, 0);
    }
  };
  auto Add = [&](vector<array<int, 3>> a) {
    for (auto[t, x, v] : a) {
      pref.modify(x, v + x, 1);
      suf.modify(x, v - x, 1);
    }
  };
  
  vector<int> ans(Q);
  int exists = 0;
  for (auto[foo, t] : events) {
    debug(foo, t);
    if (t < 0) {
      t = ~t;
      debug(T[t]);
      if (--acts[T[t]][X[t]] == 0) {
        Rem(Updates(T[t], X[t])); 
        acts[T[t]].erase(X[t]);
        Add(Updates(T[t], X[t]));
      }
      exists -= (acts[T[t]].empty());    
    } else if (t < N) {
      exists += (acts[T[t]].empty());
      if (!acts[T[t]].count(X[t])) {
        Rem(Updates(T[t], X[t])); 
        acts[T[t]][X[t]] = 0;
        Add(Updates(T[t], X[t]));
      } 
      acts[T[t]][X[t]]++;
    } else {
      t -= N;
      ans[t] = (exists == K ? max(pref.get(1, L[t]) - L[t], suf.get(L[t], POS) + L[t]) : -1);
    }
  }
  for (int i = 0; i < Q; ++i) {
    cout << ans[i] << '\n';
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 2996 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2876 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 3 ms 2648 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2860 KB Output is correct
25 Correct 2 ms 2908 KB Output is correct
26 Correct 2 ms 2848 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2676 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 2996 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2876 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 3 ms 2648 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2860 KB Output is correct
25 Correct 2 ms 2908 KB Output is correct
26 Correct 2 ms 2848 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2676 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 723 ms 143552 KB Output is correct
32 Correct 52 ms 4820 KB Output is correct
33 Correct 666 ms 137792 KB Output is correct
34 Correct 612 ms 130960 KB Output is correct
35 Correct 736 ms 145276 KB Output is correct
36 Correct 714 ms 147096 KB Output is correct
37 Correct 458 ms 133272 KB Output is correct
38 Correct 485 ms 134868 KB Output is correct
39 Correct 385 ms 130192 KB Output is correct
40 Correct 438 ms 133168 KB Output is correct
41 Correct 346 ms 73040 KB Output is correct
42 Correct 343 ms 73392 KB Output is correct
43 Correct 42 ms 6392 KB Output is correct
44 Correct 321 ms 73136 KB Output is correct
45 Correct 351 ms 73256 KB Output is correct
46 Correct 298 ms 73140 KB Output is correct
47 Correct 221 ms 58420 KB Output is correct
48 Correct 218 ms 63404 KB Output is correct
49 Correct 263 ms 68784 KB Output is correct
50 Correct 282 ms 65704 KB Output is correct
51 Correct 264 ms 70424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3218 ms 325980 KB Output is correct
2 Correct 4073 ms 472744 KB Output is correct
3 Correct 1164 ms 116612 KB Output is correct
4 Correct 2995 ms 279312 KB Output is correct
5 Correct 3666 ms 469208 KB Output is correct
6 Correct 4006 ms 470008 KB Output is correct
7 Correct 1022 ms 113652 KB Output is correct
8 Correct 2223 ms 265676 KB Output is correct
9 Correct 2470 ms 374016 KB Output is correct
10 Correct 3216 ms 468496 KB Output is correct
11 Correct 2023 ms 454904 KB Output is correct
12 Correct 2067 ms 452388 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4352 ms 622740 KB Output is correct
2 Correct 224 ms 20680 KB Output is correct
3 Correct 4511 ms 625656 KB Output is correct
4 Correct 1325 ms 114612 KB Output is correct
5 Correct 3225 ms 380540 KB Output is correct
6 Correct 2913 ms 301192 KB Output is correct
7 Correct 4237 ms 623312 KB Output is correct
8 Correct 4642 ms 624996 KB Output is correct
9 Correct 1315 ms 115900 KB Output is correct
10 Correct 3080 ms 380828 KB Output is correct
11 Correct 3672 ms 528564 KB Output is correct
12 Correct 4374 ms 630628 KB Output is correct
13 Correct 1877 ms 622076 KB Output is correct
14 Correct 1873 ms 620360 KB Output is correct
15 Correct 2180 ms 622428 KB Output is correct
16 Correct 2340 ms 623864 KB Output is correct
17 Correct 2403 ms 622024 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 2996 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2876 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 3 ms 2648 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2860 KB Output is correct
25 Correct 2 ms 2908 KB Output is correct
26 Correct 2 ms 2848 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2676 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 723 ms 143552 KB Output is correct
32 Correct 52 ms 4820 KB Output is correct
33 Correct 666 ms 137792 KB Output is correct
34 Correct 612 ms 130960 KB Output is correct
35 Correct 736 ms 145276 KB Output is correct
36 Correct 714 ms 147096 KB Output is correct
37 Correct 458 ms 133272 KB Output is correct
38 Correct 485 ms 134868 KB Output is correct
39 Correct 385 ms 130192 KB Output is correct
40 Correct 438 ms 133168 KB Output is correct
41 Correct 346 ms 73040 KB Output is correct
42 Correct 343 ms 73392 KB Output is correct
43 Correct 42 ms 6392 KB Output is correct
44 Correct 321 ms 73136 KB Output is correct
45 Correct 351 ms 73256 KB Output is correct
46 Correct 298 ms 73140 KB Output is correct
47 Correct 221 ms 58420 KB Output is correct
48 Correct 218 ms 63404 KB Output is correct
49 Correct 263 ms 68784 KB Output is correct
50 Correct 282 ms 65704 KB Output is correct
51 Correct 264 ms 70424 KB Output is correct
52 Correct 198 ms 23496 KB Output is correct
53 Correct 209 ms 14684 KB Output is correct
54 Correct 377 ms 69552 KB Output is correct
55 Correct 327 ms 59060 KB Output is correct
56 Correct 293 ms 51752 KB Output is correct
57 Correct 346 ms 68944 KB Output is correct
58 Correct 319 ms 57512 KB Output is correct
59 Correct 294 ms 50104 KB Output is correct
60 Correct 319 ms 67756 KB Output is correct
61 Correct 160 ms 23244 KB Output is correct
62 Correct 210 ms 23904 KB Output is correct
63 Correct 321 ms 48600 KB Output is correct
64 Correct 420 ms 60104 KB Output is correct
65 Correct 371 ms 67256 KB Output is correct
66 Correct 374 ms 72876 KB Output is correct
67 Correct 307 ms 7888 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 372 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 2996 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 2908 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Correct 2 ms 2876 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 3 ms 2648 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2860 KB Output is correct
25 Correct 2 ms 2908 KB Output is correct
26 Correct 2 ms 2848 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2676 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 723 ms 143552 KB Output is correct
32 Correct 52 ms 4820 KB Output is correct
33 Correct 666 ms 137792 KB Output is correct
34 Correct 612 ms 130960 KB Output is correct
35 Correct 736 ms 145276 KB Output is correct
36 Correct 714 ms 147096 KB Output is correct
37 Correct 458 ms 133272 KB Output is correct
38 Correct 485 ms 134868 KB Output is correct
39 Correct 385 ms 130192 KB Output is correct
40 Correct 438 ms 133168 KB Output is correct
41 Correct 346 ms 73040 KB Output is correct
42 Correct 343 ms 73392 KB Output is correct
43 Correct 42 ms 6392 KB Output is correct
44 Correct 321 ms 73136 KB Output is correct
45 Correct 351 ms 73256 KB Output is correct
46 Correct 298 ms 73140 KB Output is correct
47 Correct 221 ms 58420 KB Output is correct
48 Correct 218 ms 63404 KB Output is correct
49 Correct 263 ms 68784 KB Output is correct
50 Correct 282 ms 65704 KB Output is correct
51 Correct 264 ms 70424 KB Output is correct
52 Correct 3218 ms 325980 KB Output is correct
53 Correct 4073 ms 472744 KB Output is correct
54 Correct 1164 ms 116612 KB Output is correct
55 Correct 2995 ms 279312 KB Output is correct
56 Correct 3666 ms 469208 KB Output is correct
57 Correct 4006 ms 470008 KB Output is correct
58 Correct 1022 ms 113652 KB Output is correct
59 Correct 2223 ms 265676 KB Output is correct
60 Correct 2470 ms 374016 KB Output is correct
61 Correct 3216 ms 468496 KB Output is correct
62 Correct 2023 ms 454904 KB Output is correct
63 Correct 2067 ms 452388 KB Output is correct
64 Correct 4352 ms 622740 KB Output is correct
65 Correct 224 ms 20680 KB Output is correct
66 Correct 4511 ms 625656 KB Output is correct
67 Correct 1325 ms 114612 KB Output is correct
68 Correct 3225 ms 380540 KB Output is correct
69 Correct 2913 ms 301192 KB Output is correct
70 Correct 4237 ms 623312 KB Output is correct
71 Correct 4642 ms 624996 KB Output is correct
72 Correct 1315 ms 115900 KB Output is correct
73 Correct 3080 ms 380828 KB Output is correct
74 Correct 3672 ms 528564 KB Output is correct
75 Correct 4374 ms 630628 KB Output is correct
76 Correct 1877 ms 622076 KB Output is correct
77 Correct 1873 ms 620360 KB Output is correct
78 Correct 2180 ms 622428 KB Output is correct
79 Correct 2340 ms 623864 KB Output is correct
80 Correct 2403 ms 622024 KB Output is correct
81 Correct 198 ms 23496 KB Output is correct
82 Correct 209 ms 14684 KB Output is correct
83 Correct 377 ms 69552 KB Output is correct
84 Correct 327 ms 59060 KB Output is correct
85 Correct 293 ms 51752 KB Output is correct
86 Correct 346 ms 68944 KB Output is correct
87 Correct 319 ms 57512 KB Output is correct
88 Correct 294 ms 50104 KB Output is correct
89 Correct 319 ms 67756 KB Output is correct
90 Correct 160 ms 23244 KB Output is correct
91 Correct 210 ms 23904 KB Output is correct
92 Correct 321 ms 48600 KB Output is correct
93 Correct 420 ms 60104 KB Output is correct
94 Correct 371 ms 67256 KB Output is correct
95 Correct 374 ms 72876 KB Output is correct
96 Correct 307 ms 7888 KB Output is correct
97 Correct 1330 ms 116680 KB Output is correct
98 Correct 271 ms 21452 KB Output is correct
99 Correct 4556 ms 591636 KB Output is correct
100 Correct 1336 ms 72164 KB Output is correct
101 Correct 3021 ms 303328 KB Output is correct
102 Correct 4597 ms 627424 KB Output is correct
103 Correct 3034 ms 571900 KB Output is correct
104 Correct 2909 ms 571352 KB Output is correct
105 Correct 2057 ms 567980 KB Output is correct
106 Correct 2032 ms 567376 KB Output is correct
107 Correct 2008 ms 254980 KB Output is correct
108 Correct 1894 ms 234584 KB Output is correct
109 Correct 2080 ms 332640 KB Output is correct
110 Correct 2086 ms 248724 KB Output is correct
111 Correct 2037 ms 228308 KB Output is correct
112 Correct 2195 ms 326716 KB Output is correct
113 Correct 882 ms 115328 KB Output is correct
114 Correct 1363 ms 117136 KB Output is correct
115 Correct 2597 ms 217696 KB Output is correct
116 Correct 2970 ms 246624 KB Output is correct
117 Correct 3116 ms 283548 KB Output is correct
118 Correct 2376 ms 324700 KB Output is correct
119 Correct 2389 ms 38436 KB Output is correct
120 Correct 951 ms 211296 KB Output is correct
121 Correct 1183 ms 321028 KB Output is correct
122 Correct 1140 ms 320100 KB Output is correct
123 Correct 1368 ms 319680 KB Output is correct
124 Correct 1435 ms 320608 KB Output is correct
125 Correct 1293 ms 319460 KB Output is correct
126 Correct 1425 ms 274868 KB Output is correct