oj.uz

Submission #1029606

# Submission time Handle Problem Language Result Execution time Memory
1029606 2024-07-21T05:43:01 Z erray New Home (APIO18_new_home) C++17
57 / 100
 4040 ms 974176 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(2e7);

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 344 KB Output is correct
2 Correct 0 ms 344 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 2908 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2652 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 2904 KB Output is correct
12 Correct 3 ms 2904 KB Output is correct
13 Correct 2 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 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 604 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 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2648 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2652 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 344 KB Output is correct
2 Correct 0 ms 344 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 2908 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2652 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 2904 KB Output is correct
12 Correct 3 ms 2904 KB Output is correct
13 Correct 2 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 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 604 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 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2648 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2652 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 773 ms 138896 KB Output is correct
32 Correct 51 ms 4056 KB Output is correct
33 Correct 635 ms 134932 KB Output is correct
34 Correct 639 ms 127800 KB Output is correct
35 Correct 705 ms 142276 KB Output is correct
36 Correct 675 ms 144160 KB Output is correct
37 Correct 501 ms 130448 KB Output is correct
38 Correct 483 ms 131984 KB Output is correct
39 Correct 410 ms 127440 KB Output is correct
40 Correct 411 ms 130456 KB Output is correct
41 Correct 357 ms 70064 KB Output is correct
42 Correct 358 ms 70100 KB Output is correct
43 Correct 39 ms 4056 KB Output is correct
44 Correct 354 ms 70324 KB Output is correct
45 Correct 335 ms 70480 KB Output is correct
46 Correct 292 ms 70316 KB Output is correct
47 Correct 214 ms 55488 KB Output is correct
48 Correct 214 ms 60844 KB Output is correct
49 Correct 263 ms 66052 KB Output is correct
50 Correct 278 ms 62580 KB Output is correct
51 Correct 252 ms 67760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3237 ms 313264 KB Output is correct
2 Correct 4040 ms 472724 KB Output is correct
3 Correct 1147 ms 116808 KB Output is correct
4 Correct 2922 ms 279448 KB Output is correct
5 Correct 3746 ms 472744 KB Output is correct
6 Correct 3991 ms 472824 KB Output is correct
7 Correct 1086 ms 116732 KB Output is correct
8 Correct 2168 ms 268608 KB Output is correct
9 Correct 2569 ms 377072 KB Output is correct
10 Correct 3253 ms 471544 KB Output is correct
11 Correct 1965 ms 457564 KB Output is correct
12 Correct 2017 ms 455180 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3258 ms 974176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 2908 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2652 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 2904 KB Output is correct
12 Correct 3 ms 2904 KB Output is correct
13 Correct 2 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 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 604 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 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2648 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2652 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 773 ms 138896 KB Output is correct
32 Correct 51 ms 4056 KB Output is correct
33 Correct 635 ms 134932 KB Output is correct
34 Correct 639 ms 127800 KB Output is correct
35 Correct 705 ms 142276 KB Output is correct
36 Correct 675 ms 144160 KB Output is correct
37 Correct 501 ms 130448 KB Output is correct
38 Correct 483 ms 131984 KB Output is correct
39 Correct 410 ms 127440 KB Output is correct
40 Correct 411 ms 130456 KB Output is correct
41 Correct 357 ms 70064 KB Output is correct
42 Correct 358 ms 70100 KB Output is correct
43 Correct 39 ms 4056 KB Output is correct
44 Correct 354 ms 70324 KB Output is correct
45 Correct 335 ms 70480 KB Output is correct
46 Correct 292 ms 70316 KB Output is correct
47 Correct 214 ms 55488 KB Output is correct
48 Correct 214 ms 60844 KB Output is correct
49 Correct 263 ms 66052 KB Output is correct
50 Correct 278 ms 62580 KB Output is correct
51 Correct 252 ms 67760 KB Output is correct
52 Correct 200 ms 23752 KB Output is correct
53 Correct 199 ms 14796 KB Output is correct
54 Correct 397 ms 69552 KB Output is correct
55 Correct 319 ms 59260 KB Output is correct
56 Correct 274 ms 52408 KB Output is correct
57 Correct 372 ms 68860 KB Output is correct
58 Correct 308 ms 57516 KB Output is correct
59 Correct 305 ms 50104 KB Output is correct
60 Correct 347 ms 67752 KB Output is correct
61 Correct 157 ms 23236 KB Output is correct
62 Correct 179 ms 23756 KB Output is correct
63 Correct 355 ms 48572 KB Output is correct
64 Correct 393 ms 59844 KB Output is correct
65 Correct 398 ms 67244 KB Output is correct
66 Correct 345 ms 72884 KB Output is correct
67 Correct 311 ms 7992 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 2908 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 2652 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 2904 KB Output is correct
12 Correct 3 ms 2904 KB Output is correct
13 Correct 2 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 2652 KB Output is correct
18 Correct 2 ms 2652 KB Output is correct
19 Correct 2 ms 2652 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 604 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 2652 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Correct 2 ms 2648 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 2 ms 2652 KB Output is correct
29 Correct 2 ms 2652 KB Output is correct
30 Correct 1 ms 2652 KB Output is correct
31 Correct 773 ms 138896 KB Output is correct
32 Correct 51 ms 4056 KB Output is correct
33 Correct 635 ms 134932 KB Output is correct
34 Correct 639 ms 127800 KB Output is correct
35 Correct 705 ms 142276 KB Output is correct
36 Correct 675 ms 144160 KB Output is correct
37 Correct 501 ms 130448 KB Output is correct
38 Correct 483 ms 131984 KB Output is correct
39 Correct 410 ms 127440 KB Output is correct
40 Correct 411 ms 130456 KB Output is correct
41 Correct 357 ms 70064 KB Output is correct
42 Correct 358 ms 70100 KB Output is correct
43 Correct 39 ms 4056 KB Output is correct
44 Correct 354 ms 70324 KB Output is correct
45 Correct 335 ms 70480 KB Output is correct
46 Correct 292 ms 70316 KB Output is correct
47 Correct 214 ms 55488 KB Output is correct
48 Correct 214 ms 60844 KB Output is correct
49 Correct 263 ms 66052 KB Output is correct
50 Correct 278 ms 62580 KB Output is correct
51 Correct 252 ms 67760 KB Output is correct
52 Correct 3237 ms 313264 KB Output is correct
53 Correct 4040 ms 472724 KB Output is correct
54 Correct 1147 ms 116808 KB Output is correct
55 Correct 2922 ms 279448 KB Output is correct
56 Correct 3746 ms 472744 KB Output is correct
57 Correct 3991 ms 472824 KB Output is correct
58 Correct 1086 ms 116732 KB Output is correct
59 Correct 2168 ms 268608 KB Output is correct
60 Correct 2569 ms 377072 KB Output is correct
61 Correct 3253 ms 471544 KB Output is correct
62 Correct 1965 ms 457564 KB Output is correct
63 Correct 2017 ms 455180 KB Output is correct
64 Runtime error 3258 ms 974176 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -