oj.uz

Submission #252754

# Submission time Handle Problem Language Result Execution time Memory
252754 2020-07-26T08:23:45 Z EntityIT New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 457760 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 {
  int n;
  struct Node {
    array<vec<pair<int, int>, 1>, 2> segments;
    vec<pair<int, int>, 1> queries;
    Node()
        : segments({}),
          queries({}) {}
  };
  vec<Node, 1> nodes;
  IT(int t_n, const vec<pair<int, int>, 2>& queries_time_marks)
      : n(t_n),
        nodes(n << 1) {
    for (int i = 0; i < n; ++i) {
      nodes[i + n].queries = queries_time_marks[i];
    }
    for (int i = n - 1; i; --i) {
      merge(ALL(nodes[i << 1].queries), ALL(nodes[i << 1 | 1].queries), back_inserter(nodes[i].queries));
    }
  }

  void InsertSegment(int be, int en, bool slope, pair<int, int> val) {
    for (be += n, en += n; be < en; be >>= 1, en >>= 1) {
      if (be & 1) {
        nodes[be++].segments[slope].emplace_back(val);
      }
      if (en & 1) {
        nodes[--en].segments[slope].emplace_back(val);
      }
    }
  }
};

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; time_marks.reserve((n_stores << 1) + n_queries);

  vec<tuple<int, int, int, bool>, 1> changes; changes.reserve(n_stores << 1);
  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; segments[0].reserve(SZ(changes) << 1); segments[1].reserve(SZ(changes) << 1);
  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]);
      cur_time = static_cast<int>(lower_bound(ALL(time_marks), cur_time) - time_marks.begin());

      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);
          if (get<2>(segments[true].back()) == get<3>(segments[true].back())) {
            segments[true].pop_back();
          }
          begin_times_types[true][type].erase(make_pair(2, b));
        } else if (b > kMaxX) {
          segments[false].emplace_back(a, kMaxX, begin_times_types[false][type][make_pair(a, kMaxX)], cur_time);
          if (get<2>(segments[false].back()) == get<3>(segments[false].back())) {
            segments[false].pop_back();
          }
          begin_times_types[false][type].erase(make_pair(a, kMaxX));
        } else {
          segments[false].emplace_back(a, (a + b) >> 1, begin_times_types[false][type][make_pair(a, (a + b) >> 1)], cur_time);
          if (get<2>(segments[false].back()) == get<3>(segments[false].back())) {
            segments[false].pop_back();
          }
          begin_times_types[false][type].erase(make_pair(a, (a + b) >> 1));
          segments[true].emplace_back((a + b) >> 1, b, begin_times_types[true][type][make_pair((a + b) >> 1, b)], cur_time);
          if (get<2>(segments[true].back()) == get<3>(segments[true].back())) {
            segments[true].pop_back();
          }
          begin_times_types[true][type].erase(make_pair((a + b) >> 1, b));
        }
      };

      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));
  }

  cerr << clock() * 1000 / CLOCKS_PER_SEC << "ms\n";

  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;
    it.InsertSegment(be_time, en_time, true, make_pair(l_x, r_x));
  }

  cerr << clock() * 1000 / CLOCKS_PER_SEC << "ms\n";

  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;
    it.InsertSegment(be_time, en_time, false, make_pair(l_x, r_x));
  }

  cerr << clock() * 1000 / CLOCKS_PER_SEC << "ms\n";

  for (int i = 1; i < SZ(it.nodes); ++i) {
    int max_x = 0;
    auto it_segments = it.nodes[i].segments[true].begin();
    for (auto& query : it.nodes[i].queries) {
      for (; it_segments != it.nodes[i].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 = it.nodes[i].segments[false].begin();
    reverse(ALL(it.nodes[i].queries));
    for (auto& query : it.nodes[i].queries) {
      for (; it_segments != it.nodes[i].segments[false].end() && it_segments->second >= query.first; ++it_segments) {
        Minimize(min_x, it_segments->first);
      }
      Maximize(answers[query.second], query.first - min_x);
    }
  }

  cerr << clock() * 1000 / CLOCKS_PER_SEC << "ms\n";

  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 0 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 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 3 ms 896 KB Output is correct
16 Correct 3 ms 896 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 4 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 3 ms 896 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 2 ms 768 KB Output is correct
30 Correct 2 ms 640 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 3 ms 896 KB Output is correct
16 Correct 3 ms 896 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 4 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 3 ms 896 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 2 ms 768 KB Output is correct
30 Correct 2 ms 640 KB Output is correct
31 Correct 1114 ms 119696 KB Output is correct
32 Correct 68 ms 7308 KB Output is correct
33 Correct 951 ms 115552 KB Output is correct
34 Correct 983 ms 113384 KB Output is correct
35 Correct 1099 ms 120864 KB Output is correct
36 Correct 1153 ms 121036 KB Output is correct
37 Correct 755 ms 107144 KB Output is correct
38 Correct 788 ms 107408 KB Output is correct
39 Correct 589 ms 94324 KB Output is correct
40 Correct 624 ms 97544 KB Output is correct
41 Correct 661 ms 90728 KB Output is correct
42 Correct 790 ms 83104 KB Output is correct
43 Correct 73 ms 6792 KB Output is correct
44 Correct 715 ms 89480 KB Output is correct
45 Correct 612 ms 84744 KB Output is correct
46 Correct 531 ms 75784 KB Output is correct
47 Correct 336 ms 65132 KB Output is correct
48 Correct 312 ms 67592 KB Output is correct
49 Correct 379 ms 73308 KB Output is correct
50 Correct 413 ms 78072 KB Output is correct
51 Correct 371 ms 72248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1852 ms 328192 KB Output is correct
2 Correct 1546 ms 315672 KB Output is correct
3 Correct 1415 ms 373528 KB Output is correct
4 Correct 1655 ms 336024 KB Output is correct
5 Correct 1711 ms 315548 KB Output is correct
6 Correct 1522 ms 315972 KB Output is correct
7 Correct 1342 ms 373396 KB Output is correct
8 Correct 1676 ms 335892 KB Output is correct
9 Correct 2090 ms 322728 KB Output is correct
10 Correct 2025 ms 316260 KB Output is correct
11 Correct 1449 ms 312600 KB Output is correct
12 Correct 1839 ms 315148 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4927 ms 435448 KB Output is correct
2 Correct 341 ms 35592 KB Output is correct
3 Execution timed out 5081 ms 457760 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 3 ms 896 KB Output is correct
16 Correct 3 ms 896 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 4 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 3 ms 896 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 2 ms 768 KB Output is correct
30 Correct 2 ms 640 KB Output is correct
31 Correct 1114 ms 119696 KB Output is correct
32 Correct 68 ms 7308 KB Output is correct
33 Correct 951 ms 115552 KB Output is correct
34 Correct 983 ms 113384 KB Output is correct
35 Correct 1099 ms 120864 KB Output is correct
36 Correct 1153 ms 121036 KB Output is correct
37 Correct 755 ms 107144 KB Output is correct
38 Correct 788 ms 107408 KB Output is correct
39 Correct 589 ms 94324 KB Output is correct
40 Correct 624 ms 97544 KB Output is correct
41 Correct 661 ms 90728 KB Output is correct
42 Correct 790 ms 83104 KB Output is correct
43 Correct 73 ms 6792 KB Output is correct
44 Correct 715 ms 89480 KB Output is correct
45 Correct 612 ms 84744 KB Output is correct
46 Correct 531 ms 75784 KB Output is correct
47 Correct 336 ms 65132 KB Output is correct
48 Correct 312 ms 67592 KB Output is correct
49 Correct 379 ms 73308 KB Output is correct
50 Correct 413 ms 78072 KB Output is correct
51 Correct 371 ms 72248 KB Output is correct
52 Correct 418 ms 76388 KB Output is correct
53 Correct 436 ms 75488 KB Output is correct
54 Correct 797 ms 86708 KB Output is correct
55 Correct 588 ms 91016 KB Output is correct
56 Correct 522 ms 91732 KB Output is correct
57 Correct 614 ms 91272 KB Output is correct
58 Correct 678 ms 86276 KB Output is correct
59 Correct 544 ms 84312 KB Output is correct
60 Correct 596 ms 86188 KB Output is correct
61 Correct 106 ms 35504 KB Output is correct
62 Correct 420 ms 79756 KB Output is correct
63 Correct 570 ms 87052 KB Output is correct
64 Correct 617 ms 91660 KB Output is correct
65 Correct 684 ms 96864 KB Output is correct
66 Correct 729 ms 94928 KB Output is correct
67 Correct 271 ms 21644 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 3 ms 896 KB Output is correct
16 Correct 3 ms 896 KB Output is correct
17 Correct 3 ms 896 KB Output is correct
18 Correct 3 ms 896 KB Output is correct
19 Correct 3 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 4 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 3 ms 896 KB Output is correct
27 Correct 2 ms 512 KB Output is correct
28 Correct 2 ms 768 KB Output is correct
29 Correct 2 ms 768 KB Output is correct
30 Correct 2 ms 640 KB Output is correct
31 Correct 1114 ms 119696 KB Output is correct
32 Correct 68 ms 7308 KB Output is correct
33 Correct 951 ms 115552 KB Output is correct
34 Correct 983 ms 113384 KB Output is correct
35 Correct 1099 ms 120864 KB Output is correct
36 Correct 1153 ms 121036 KB Output is correct
37 Correct 755 ms 107144 KB Output is correct
38 Correct 788 ms 107408 KB Output is correct
39 Correct 589 ms 94324 KB Output is correct
40 Correct 624 ms 97544 KB Output is correct
41 Correct 661 ms 90728 KB Output is correct
42 Correct 790 ms 83104 KB Output is correct
43 Correct 73 ms 6792 KB Output is correct
44 Correct 715 ms 89480 KB Output is correct
45 Correct 612 ms 84744 KB Output is correct
46 Correct 531 ms 75784 KB Output is correct
47 Correct 336 ms 65132 KB Output is correct
48 Correct 312 ms 67592 KB Output is correct
49 Correct 379 ms 73308 KB Output is correct
50 Correct 413 ms 78072 KB Output is correct
51 Correct 371 ms 72248 KB Output is correct
52 Correct 1852 ms 328192 KB Output is correct
53 Correct 1546 ms 315672 KB Output is correct
54 Correct 1415 ms 373528 KB Output is correct
55 Correct 1655 ms 336024 KB Output is correct
56 Correct 1711 ms 315548 KB Output is correct
57 Correct 1522 ms 315972 KB Output is correct
58 Correct 1342 ms 373396 KB Output is correct
59 Correct 1676 ms 335892 KB Output is correct
60 Correct 2090 ms 322728 KB Output is correct
61 Correct 2025 ms 316260 KB Output is correct
62 Correct 1449 ms 312600 KB Output is correct
63 Correct 1839 ms 315148 KB Output is correct
64 Correct 4927 ms 435448 KB Output is correct
65 Correct 341 ms 35592 KB Output is correct
66 Execution timed out 5081 ms 457760 KB Time limit exceeded
67 Halted 0 ms 0 KB -