oj.uz

Submission #252696

# Submission time Handle Problem Language Result Execution time Memory
252696 2020-07-26T06:53:48 Z EntityIT New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 499736 KB 
#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) static_cast<int>((x).size())

template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
      : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
      : vector<T>(args...) {}
};

template<class T>
inline bool Minimize(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool Maximize(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int Next(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int Prev(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));

struct IT {
  struct Node {
    Node* l_child,* r_child;
    array<vec<pair<int, int>, 1>, 2> segments;
    vec<pair<int, int>, 1> queries;
    Node(Node* t_left_child, Node* t_right_child, vec<pair<int, int>, 1> t_queries)
        : l_child(t_left_child),
          r_child(t_right_child),
          segments({}),
          queries(t_queries) {}
  };
  Node* root;
  int n;
  IT(int t_n, vec<pair<int, int>, 2> queries_time_marks)
      : n(t_n) {
    function<Node*(int, int)> Build = [&](int l_pos, int r_pos) {
      if (l_pos == r_pos) {
        return new Node(nullptr, nullptr, queries_time_marks[l_pos]);
      }
      int m_pos = (l_pos + r_pos) >> 1;
      Node* node = new Node(Build(l_pos, m_pos), Build(m_pos + 1, r_pos), vec<pair<int, int>, 1>());
      merge(ALL(node->l_child->queries), ALL(node->r_child->queries), back_inserter(node->queries));
      return node;
    };
    root = Build(0, n - 1);
  }

  void InsertSegment(int l, int r, bool slope, pair<int, int> val, Node* node, int l_pos, int r_pos) {
    if (r < l_pos || r_pos < l) {
      return;
    }
    if (l <= l_pos && r_pos <= r) {
      node->segments[slope].emplace_back(val);
      return;
    }
    int m_pos = (l_pos + r_pos) >> 1;
    InsertSegment(l, r, slope, val, node->l_child, l_pos, m_pos);
    InsertSegment(l, r, slope, val, node->r_child, m_pos + 1, r_pos);
  }
  void InsertSegment(int l, int r, bool slope, pair<int, int> val) {
    InsertSegment(l, r, slope, val, root, 0, n - 1);
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  constexpr int kMaxX = 2e8;

  int n_stores, n_types, n_queries; cin >> n_stores >> n_types >> n_queries;

  vec<int, 1> time_marks;

  vec<tuple<int, int, int, bool>, 1> changes;
  while (n_stores--) {
    int x, type, l, r; cin >> x >> type >> l >> r; x <<= 1; --type;
    changes.emplace_back(l, x, type, true);
    changes.emplace_back(r + 1, x, type, false);
    time_marks.emplace_back(l);
    time_marks.emplace_back(r + 1);
  }
  sort(ALL(changes));

  vec<pair<int, int>, 1> queries(n_queries);
  for (auto& i : queries) {
    cin >> i.first >> i.second; i.first <<= 1;
    time_marks.emplace_back(i.second);
  }

  sort(ALL(time_marks));
  time_marks.erase(unique(ALL(time_marks)), time_marks.end());

  vec<int, 1> answers(n_queries);
  vec<int, 1> ord_queries(n_queries); iota(ALL(ord_queries), 0);
  sort(ALL(ord_queries), [&](int i, int j) { return queries[i].second < queries[j].second; });
  ord_queries.emplace_back(-1);
  array<vec<map<pair<int, int>, int>, 1>, 2> begin_times_types{vec<map<pair<int, int>, int>, 1>(n_types), vec<map<pair<int, int>, int>, 1>(n_types)};
  array<vec<tuple<int, int, int, int>, 1>, 2> segments;
  for (auto& i_query : ord_queries) {
    static auto it_changes = changes.begin();
    static int n_open_types = 0;
    static vec<set<int>, 1> xs_types(n_types);
    static vec<map<int, int>, 1> n_occurrences_types(n_types);

    for (; it_changes != changes.end() && (!~i_query || get<0>(*it_changes) <= queries[i_query].second); ++it_changes) {
      int cur_time, x, type; bool insertion; tie(cur_time, x, type, insertion) = *it_changes;
      n_open_types -= !!SZ(xs_types[type]);

      auto Insert = [&](int a, int b) {
        if (!a) {
          begin_times_types[true][type][make_pair(2, b)] = cur_time;
        } else if (b > kMaxX) {
          begin_times_types[false][type][make_pair(a, kMaxX)] = cur_time;
        } else {
          begin_times_types[false][type][make_pair(a, (a + b) >> 1)] = begin_times_types[true][type][make_pair((a + b) >> 1, b)] = cur_time;
        }
      };
      auto Erase = [&](int a, int b) {
        if (!a) {
          segments[true].emplace_back(2, b, begin_times_types[true][type][make_pair(2, b)], cur_time);
        } else if (b > kMaxX) {
          segments[false].emplace_back(a, kMaxX, begin_times_types[false][type][make_pair(a, kMaxX)], cur_time);
        } else {
          segments[false].emplace_back(a, (a + b) >> 1, begin_times_types[false][type][make_pair(a, (a + b) >> 1)], cur_time);
          segments[true].emplace_back((a + b) >> 1, b, begin_times_types[true][type][make_pair((a + b) >> 1, b)], cur_time);
        }
      };

      if (insertion) {
        if ((++n_occurrences_types[type][x]) == 1) {
          auto it = xs_types[type].emplace(x).first;
          if (it == xs_types[type].begin() && next(it) == xs_types[type].end()) {
            Insert(0, x); Insert(x, kMaxX + 2);
          } else if (it == xs_types[type].begin()) {
            Erase(0, *next(it));
            Insert(0, x); Insert(x, *next(it));
          } else if (next(it) == xs_types[type].end()) {
            Erase(*prev(it), kMaxX + 2);
            Insert(*prev(it), x); Insert(x, kMaxX + 2);
          } else {
            Erase(*prev(it), *next(it));
            Insert(*prev(it), x); Insert(x, *next(it));
          }
        }
      } else {
        if (!(--n_occurrences_types[type][x])) {
          auto it = xs_types[type].find(x);
          assert(it != xs_types[type].end());
          if (it == xs_types[type].begin() && next(it) == xs_types[type].end()) {
            Erase(0, x); Erase(x, kMaxX + 2);
          } else if (it == xs_types[type].begin()) {
            Erase(0, x); Erase(x, *next(it));
            Insert(0, *next(it));
          } else if (next(it) == xs_types[type].end()) {
            Erase(*prev(it), x); Erase(x, kMaxX + 2);
            Insert(*prev(it), kMaxX + 2);
          } else {
            Erase(*prev(it), x); Erase(x, *next(it));
            Insert(*prev(it), *next(it));
          }
          xs_types[type].erase(it);
        }
      }
      n_open_types += !!SZ(xs_types[type]);
    }

    if (n_open_types != n_types && ~i_query) {
      answers[i_query] = -1;
    }
  }

  vec<pair<int, int>, 2> queries_time_marks(SZ(time_marks));
  for (int i = 0; i < n_queries; ++i) {
    if (answers[i]) {
      continue;
    }
    queries_time_marks[static_cast<int>(lower_bound(ALL(time_marks), queries[i].second) - time_marks.begin())].emplace_back(queries[i].first, i);
  }
  for (auto& queries_time_mark : queries_time_marks) {
    sort(ALL(queries_time_mark));
  }

  IT it(SZ(time_marks), queries_time_marks);

  sort(ALL(segments[true]));
  for (auto& segment : segments[true]) {
    int l_x, r_x, be_time, en_time; tie(l_x, r_x, be_time, en_time) = segment;
    if (be_time == en_time) {
      continue;
    }
    int l_time_mark = static_cast<int>(lower_bound(ALL(time_marks), be_time) - time_marks.begin()), r_time_mark = static_cast<int>(lower_bound(ALL(time_marks), en_time) - time_marks.begin()) - 1;
    it.InsertSegment(l_time_mark, r_time_mark, true, make_pair(l_x, r_x));
  }

  sort(ALL(segments[false]), [&](auto i, auto j) { return get<1>(i) > get<1>(j); });
  for (auto& segment : segments[false]) {
    int l_x, r_x, be_time, en_time; tie(l_x, r_x, be_time, en_time) = segment;
    if (be_time == en_time) {
      continue;
    }
    int l_time_mark = static_cast<int>(lower_bound(ALL(time_marks), be_time) - time_marks.begin()), r_time_mark = static_cast<int>(lower_bound(ALL(time_marks), en_time) - time_marks.begin()) - 1;
    it.InsertSegment(l_time_mark, r_time_mark, false, make_pair(l_x, r_x));
  }

  function<void(IT::Node*)> Solve = [&](IT::Node* node) {
    if (node == nullptr) {
      return;
    }

    int max_x = 0;
    auto it_segments = node->segments[true].begin();
    for (auto& query : node->queries) {
      for (; it_segments != node->segments[true].end() && it_segments->first <= query.first; ++it_segments) {
        Maximize(max_x, it_segments->second);
      }
      Maximize(answers[query.second], max_x - query.first);
    }

    int min_x = kMaxX;
    it_segments = node->segments[false].begin();
    reverse(ALL(node->queries));
    for (auto& query : node->queries) {
      for (; it_segments != node->segments[false].end() && it_segments->second >= query.first; ++it_segments) {
        Minimize(min_x, it_segments->first);
      }
      Maximize(answers[query.second], query.first - min_x);
    }

    Solve(node->l_child); Solve(node->r_child);
  };
  Solve(it.root);

  for (auto& answer : answers) {
    cout << (~answer ? answer >> 1 : -1) << '\n';
  }

  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 4 ms 1152 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 3 ms 896 KB Output is correct
15 Correct 3 ms 1024 KB Output is correct
16 Correct 3 ms 1024 KB Output is correct
17 Correct 3 ms 1024 KB Output is correct
18 Correct 3 ms 1024 KB Output is correct
19 Correct 3 ms 1024 KB Output is correct
20 Correct 3 ms 1024 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 3 ms 1024 KB Output is correct
25 Correct 4 ms 1024 KB Output is correct
26 Correct 3 ms 1024 KB Output is correct
27 Correct 2 ms 640 KB Output is correct
28 Correct 3 ms 896 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 2 ms 768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 4 ms 1152 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 3 ms 896 KB Output is correct
15 Correct 3 ms 1024 KB Output is correct
16 Correct 3 ms 1024 KB Output is correct
17 Correct 3 ms 1024 KB Output is correct
18 Correct 3 ms 1024 KB Output is correct
19 Correct 3 ms 1024 KB Output is correct
20 Correct 3 ms 1024 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 3 ms 1024 KB Output is correct
25 Correct 4 ms 1024 KB Output is correct
26 Correct 3 ms 1024 KB Output is correct
27 Correct 2 ms 640 KB Output is correct
28 Correct 3 ms 896 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 2 ms 768 KB Output is correct
31 Correct 1716 ms 143912 KB Output is correct
32 Correct 71 ms 8872 KB Output is correct
33 Correct 1692 ms 148972 KB Output is correct
34 Correct 1846 ms 146524 KB Output is correct
35 Correct 1513 ms 147136 KB Output is correct
36 Correct 1801 ms 147736 KB Output is correct
37 Correct 1062 ms 140696 KB Output is correct
38 Correct 1050 ms 141068 KB Output is correct
39 Correct 801 ms 126236 KB Output is correct
40 Correct 857 ms 130204 KB Output is correct
41 Correct 1174 ms 116904 KB Output is correct
42 Correct 1119 ms 109736 KB Output is correct
43 Correct 63 ms 10280 KB Output is correct
44 Correct 1120 ms 115916 KB Output is correct
45 Correct 1082 ms 111400 KB Output is correct
46 Correct 950 ms 102568 KB Output is correct
47 Correct 525 ms 90404 KB Output is correct
48 Correct 540 ms 92484 KB Output is correct
49 Correct 616 ms 99456 KB Output is correct
50 Correct 699 ms 103872 KB Output is correct
51 Correct 634 ms 98452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2117 ms 408448 KB Output is correct
2 Correct 1987 ms 408960 KB Output is correct
3 Correct 1622 ms 420424 KB Output is correct
4 Correct 2070 ms 411732 KB Output is correct
5 Correct 1991 ms 408308 KB Output is correct
6 Correct 2077 ms 409088 KB Output is correct
7 Correct 1788 ms 420416 KB Output is correct
8 Correct 2013 ms 415196 KB Output is correct
9 Correct 2391 ms 411212 KB Output is correct
10 Correct 2310 ms 409732 KB Output is correct
11 Correct 1893 ms 406668 KB Output is correct
12 Correct 2142 ms 408448 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5118 ms 499736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 4 ms 1152 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 3 ms 896 KB Output is correct
15 Correct 3 ms 1024 KB Output is correct
16 Correct 3 ms 1024 KB Output is correct
17 Correct 3 ms 1024 KB Output is correct
18 Correct 3 ms 1024 KB Output is correct
19 Correct 3 ms 1024 KB Output is correct
20 Correct 3 ms 1024 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 3 ms 1024 KB Output is correct
25 Correct 4 ms 1024 KB Output is correct
26 Correct 3 ms 1024 KB Output is correct
27 Correct 2 ms 640 KB Output is correct
28 Correct 3 ms 896 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 2 ms 768 KB Output is correct
31 Correct 1716 ms 143912 KB Output is correct
32 Correct 71 ms 8872 KB Output is correct
33 Correct 1692 ms 148972 KB Output is correct
34 Correct 1846 ms 146524 KB Output is correct
35 Correct 1513 ms 147136 KB Output is correct
36 Correct 1801 ms 147736 KB Output is correct
37 Correct 1062 ms 140696 KB Output is correct
38 Correct 1050 ms 141068 KB Output is correct
39 Correct 801 ms 126236 KB Output is correct
40 Correct 857 ms 130204 KB Output is correct
41 Correct 1174 ms 116904 KB Output is correct
42 Correct 1119 ms 109736 KB Output is correct
43 Correct 63 ms 10280 KB Output is correct
44 Correct 1120 ms 115916 KB Output is correct
45 Correct 1082 ms 111400 KB Output is correct
46 Correct 950 ms 102568 KB Output is correct
47 Correct 525 ms 90404 KB Output is correct
48 Correct 540 ms 92484 KB Output is correct
49 Correct 616 ms 99456 KB Output is correct
50 Correct 699 ms 103872 KB Output is correct
51 Correct 634 ms 98452 KB Output is correct
52 Correct 503 ms 92712 KB Output is correct
53 Correct 487 ms 94256 KB Output is correct
54 Correct 862 ms 111268 KB Output is correct
55 Correct 894 ms 116988 KB Output is correct
56 Correct 808 ms 115188 KB Output is correct
57 Correct 1159 ms 116912 KB Output is correct
58 Correct 908 ms 111400 KB Output is correct
59 Correct 1109 ms 108664 KB Output is correct
60 Correct 1258 ms 111464 KB Output is correct
61 Correct 114 ms 37420 KB Output is correct
62 Correct 559 ms 102440 KB Output is correct
63 Correct 884 ms 110204 KB Output is correct
64 Correct 882 ms 116836 KB Output is correct
65 Correct 1069 ms 124080 KB Output is correct
66 Correct 1200 ms 120328 KB Output is correct
67 Correct 323 ms 35880 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 4 ms 1024 KB Output is correct
7 Correct 2 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 896 KB Output is correct
10 Correct 4 ms 1152 KB Output is correct
11 Correct 2 ms 896 KB Output is correct
12 Correct 3 ms 1024 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 3 ms 896 KB Output is correct
15 Correct 3 ms 1024 KB Output is correct
16 Correct 3 ms 1024 KB Output is correct
17 Correct 3 ms 1024 KB Output is correct
18 Correct 3 ms 1024 KB Output is correct
19 Correct 3 ms 1024 KB Output is correct
20 Correct 3 ms 1024 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 3 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct
24 Correct 3 ms 1024 KB Output is correct
25 Correct 4 ms 1024 KB Output is correct
26 Correct 3 ms 1024 KB Output is correct
27 Correct 2 ms 640 KB Output is correct
28 Correct 3 ms 896 KB Output is correct
29 Correct 3 ms 896 KB Output is correct
30 Correct 2 ms 768 KB Output is correct
31 Correct 1716 ms 143912 KB Output is correct
32 Correct 71 ms 8872 KB Output is correct
33 Correct 1692 ms 148972 KB Output is correct
34 Correct 1846 ms 146524 KB Output is correct
35 Correct 1513 ms 147136 KB Output is correct
36 Correct 1801 ms 147736 KB Output is correct
37 Correct 1062 ms 140696 KB Output is correct
38 Correct 1050 ms 141068 KB Output is correct
39 Correct 801 ms 126236 KB Output is correct
40 Correct 857 ms 130204 KB Output is correct
41 Correct 1174 ms 116904 KB Output is correct
42 Correct 1119 ms 109736 KB Output is correct
43 Correct 63 ms 10280 KB Output is correct
44 Correct 1120 ms 115916 KB Output is correct
45 Correct 1082 ms 111400 KB Output is correct
46 Correct 950 ms 102568 KB Output is correct
47 Correct 525 ms 90404 KB Output is correct
48 Correct 540 ms 92484 KB Output is correct
49 Correct 616 ms 99456 KB Output is correct
50 Correct 699 ms 103872 KB Output is correct
51 Correct 634 ms 98452 KB Output is correct
52 Correct 2117 ms 408448 KB Output is correct
53 Correct 1987 ms 408960 KB Output is correct
54 Correct 1622 ms 420424 KB Output is correct
55 Correct 2070 ms 411732 KB Output is correct
56 Correct 1991 ms 408308 KB Output is correct
57 Correct 2077 ms 409088 KB Output is correct
58 Correct 1788 ms 420416 KB Output is correct
59 Correct 2013 ms 415196 KB Output is correct
60 Correct 2391 ms 411212 KB Output is correct
61 Correct 2310 ms 409732 KB Output is correct
62 Correct 1893 ms 406668 KB Output is correct
63 Correct 2142 ms 408448 KB Output is correct
64 Execution timed out 5118 ms 499736 KB Time limit exceeded
65 Halted 0 ms 0 KB -