oj.uz

Submission #252966

# Submission time Handle Problem Language Result Execution time Memory
252966 2020-07-26T14:38:35 Z EntityIT New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 603584 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);
  vec<map<int, int>, 1> begin_times_types(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<map<int, int>, 1> n_occurrences_xs_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(n_occurrences_xs_types[type]);
      cur_time = static_cast<int>(lower_bound(ALL(time_marks), cur_time) - time_marks.begin());

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

			auto it = n_occurrences_xs_types[type].find(x);
      if (insertion) {
        if (it == n_occurrences_xs_types[type].end()) {
					it = n_occurrences_xs_types[type].emplace(x, 1).first;
          if (it == n_occurrences_xs_types[type].begin() && next(it) == n_occurrences_xs_types[type].end()) {
            Insert(0); Insert(x);
          } else if (it == n_occurrences_xs_types[type].begin()) {
            Erase(0, next(it)->first);
            Insert(0); Insert(x);
          } else if (next(it) == n_occurrences_xs_types[type].end()) {
            Erase(prev(it)->first, kMaxX + 2);
            Insert(prev(it)->first); Insert(x);
          } else {
            Erase(prev(it)->first, next(it)->first);
            Insert(prev(it)->first); Insert(x);
          }
        } else {
					++it->second;
				}
      } else {
        if (it->second == 1) {
          if (it == n_occurrences_xs_types[type].begin() && next(it) == n_occurrences_xs_types[type].end()) {
            Erase(0, x); Erase(x, kMaxX + 2);
          } else if (it == n_occurrences_xs_types[type].begin()) {
            Erase(0, x); Erase(x, next(it)->first);
            Insert(0);
          } else if (next(it) == n_occurrences_xs_types[type].end()) {
            Erase(prev(it)->first, x); Erase(x, kMaxX + 2);
            Insert(prev(it)->first);
          } else {
            Erase(prev(it)->first, x); Erase(x, next(it)->first);
            Insert(prev(it)->first);
          }
          n_occurrences_xs_types[type].erase(it);
        } else {
					--it->second;
				}
      }
      n_open_types += !!SZ(n_occurrences_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;
    it.InsertSegment(be_time, en_time, 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;
    it.InsertSegment(be_time, en_time, false, make_pair(l_x, r_x));
  }

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

  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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 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 2 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 2 ms 896 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 2 ms 896 KB Output is correct
19 Correct 2 ms 896 KB Output is correct
20 Correct 2 ms 896 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 2 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 3 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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 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 2 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 2 ms 896 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 2 ms 896 KB Output is correct
19 Correct 2 ms 896 KB Output is correct
20 Correct 2 ms 896 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 2 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 3 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 882 ms 122088 KB Output is correct
32 Correct 68 ms 8060 KB Output is correct
33 Correct 875 ms 117608 KB Output is correct
34 Correct 862 ms 115456 KB Output is correct
35 Correct 964 ms 122728 KB Output is correct
36 Correct 907 ms 122312 KB Output is correct
37 Correct 624 ms 108128 KB Output is correct
38 Correct 631 ms 108392 KB Output is correct
39 Correct 503 ms 94836 KB Output is correct
40 Correct 519 ms 98304 KB Output is correct
41 Correct 614 ms 91892 KB Output is correct
42 Correct 579 ms 84220 KB Output is correct
43 Correct 64 ms 7440 KB Output is correct
44 Correct 616 ms 90484 KB Output is correct
45 Correct 612 ms 85876 KB Output is correct
46 Correct 480 ms 76916 KB Output is correct
47 Correct 300 ms 66164 KB Output is correct
48 Correct 306 ms 68600 KB Output is correct
49 Correct 364 ms 74228 KB Output is correct
50 Correct 387 ms 78960 KB Output is correct
51 Correct 367 ms 73080 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1352 ms 313364 KB Output is correct
2 Correct 1225 ms 304020 KB Output is correct
3 Correct 1255 ms 347496 KB Output is correct
4 Correct 1335 ms 319480 KB Output is correct
5 Correct 1352 ms 304100 KB Output is correct
6 Correct 1216 ms 304756 KB Output is correct
7 Correct 1225 ms 347772 KB Output is correct
8 Correct 1285 ms 320116 KB Output is correct
9 Correct 1442 ms 310076 KB Output is correct
10 Correct 1492 ms 305384 KB Output is correct
11 Correct 1113 ms 302912 KB Output is correct
12 Correct 1313 ms 304748 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3983 ms 443788 KB Output is correct
2 Correct 313 ms 35940 KB Output is correct
3 Correct 3809 ms 460688 KB Output is correct
4 Correct 1530 ms 331036 KB Output is correct
5 Correct 2555 ms 356696 KB Output is correct
6 Correct 2352 ms 350928 KB Output is correct
7 Correct 3872 ms 485288 KB Output is correct
8 Correct 3858 ms 472824 KB Output is correct
9 Correct 1627 ms 366824 KB Output is correct
10 Correct 2677 ms 430120 KB Output is correct
11 Correct 3864 ms 467632 KB Output is correct
12 Correct 3845 ms 460448 KB Output is correct
13 Correct 1937 ms 372904 KB Output is correct
14 Correct 1948 ms 402112 KB Output is correct
15 Correct 2236 ms 426556 KB Output is correct
16 Correct 2461 ms 429532 KB Output is correct
17 Correct 2366 ms 404632 KB Output is correct

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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 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 2 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 2 ms 896 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 2 ms 896 KB Output is correct
19 Correct 2 ms 896 KB Output is correct
20 Correct 2 ms 896 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 2 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 3 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 882 ms 122088 KB Output is correct
32 Correct 68 ms 8060 KB Output is correct
33 Correct 875 ms 117608 KB Output is correct
34 Correct 862 ms 115456 KB Output is correct
35 Correct 964 ms 122728 KB Output is correct
36 Correct 907 ms 122312 KB Output is correct
37 Correct 624 ms 108128 KB Output is correct
38 Correct 631 ms 108392 KB Output is correct
39 Correct 503 ms 94836 KB Output is correct
40 Correct 519 ms 98304 KB Output is correct
41 Correct 614 ms 91892 KB Output is correct
42 Correct 579 ms 84220 KB Output is correct
43 Correct 64 ms 7440 KB Output is correct
44 Correct 616 ms 90484 KB Output is correct
45 Correct 612 ms 85876 KB Output is correct
46 Correct 480 ms 76916 KB Output is correct
47 Correct 300 ms 66164 KB Output is correct
48 Correct 306 ms 68600 KB Output is correct
49 Correct 364 ms 74228 KB Output is correct
50 Correct 387 ms 78960 KB Output is correct
51 Correct 367 ms 73080 KB Output is correct
52 Correct 384 ms 74636 KB Output is correct
53 Correct 348 ms 73084 KB Output is correct
54 Correct 543 ms 86516 KB Output is correct
55 Correct 531 ms 90608 KB Output is correct
56 Correct 491 ms 90776 KB Output is correct
57 Correct 592 ms 91380 KB Output is correct
58 Correct 535 ms 85616 KB Output is correct
59 Correct 549 ms 83696 KB Output is correct
60 Correct 610 ms 86220 KB Output is correct
61 Correct 98 ms 26624 KB Output is correct
62 Correct 357 ms 78216 KB Output is correct
63 Correct 526 ms 86788 KB Output is correct
64 Correct 553 ms 91764 KB Output is correct
65 Correct 638 ms 97152 KB Output is correct
66 Correct 673 ms 95420 KB Output is correct
67 Correct 149 ms 20488 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 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 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 2 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 2 ms 896 KB Output is correct
17 Correct 2 ms 896 KB Output is correct
18 Correct 2 ms 896 KB Output is correct
19 Correct 2 ms 896 KB Output is correct
20 Correct 2 ms 896 KB Output is correct
21 Correct 1 ms 512 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 2 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 3 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 882 ms 122088 KB Output is correct
32 Correct 68 ms 8060 KB Output is correct
33 Correct 875 ms 117608 KB Output is correct
34 Correct 862 ms 115456 KB Output is correct
35 Correct 964 ms 122728 KB Output is correct
36 Correct 907 ms 122312 KB Output is correct
37 Correct 624 ms 108128 KB Output is correct
38 Correct 631 ms 108392 KB Output is correct
39 Correct 503 ms 94836 KB Output is correct
40 Correct 519 ms 98304 KB Output is correct
41 Correct 614 ms 91892 KB Output is correct
42 Correct 579 ms 84220 KB Output is correct
43 Correct 64 ms 7440 KB Output is correct
44 Correct 616 ms 90484 KB Output is correct
45 Correct 612 ms 85876 KB Output is correct
46 Correct 480 ms 76916 KB Output is correct
47 Correct 300 ms 66164 KB Output is correct
48 Correct 306 ms 68600 KB Output is correct
49 Correct 364 ms 74228 KB Output is correct
50 Correct 387 ms 78960 KB Output is correct
51 Correct 367 ms 73080 KB Output is correct
52 Correct 1352 ms 313364 KB Output is correct
53 Correct 1225 ms 304020 KB Output is correct
54 Correct 1255 ms 347496 KB Output is correct
55 Correct 1335 ms 319480 KB Output is correct
56 Correct 1352 ms 304100 KB Output is correct
57 Correct 1216 ms 304756 KB Output is correct
58 Correct 1225 ms 347772 KB Output is correct
59 Correct 1285 ms 320116 KB Output is correct
60 Correct 1442 ms 310076 KB Output is correct
61 Correct 1492 ms 305384 KB Output is correct
62 Correct 1113 ms 302912 KB Output is correct
63 Correct 1313 ms 304748 KB Output is correct
64 Correct 3983 ms 443788 KB Output is correct
65 Correct 313 ms 35940 KB Output is correct
66 Correct 3809 ms 460688 KB Output is correct
67 Correct 1530 ms 331036 KB Output is correct
68 Correct 2555 ms 356696 KB Output is correct
69 Correct 2352 ms 350928 KB Output is correct
70 Correct 3872 ms 485288 KB Output is correct
71 Correct 3858 ms 472824 KB Output is correct
72 Correct 1627 ms 366824 KB Output is correct
73 Correct 2677 ms 430120 KB Output is correct
74 Correct 3864 ms 467632 KB Output is correct
75 Correct 3845 ms 460448 KB Output is correct
76 Correct 1937 ms 372904 KB Output is correct
77 Correct 1948 ms 402112 KB Output is correct
78 Correct 2236 ms 426556 KB Output is correct
79 Correct 2461 ms 429532 KB Output is correct
80 Correct 2366 ms 404632 KB Output is correct
81 Correct 384 ms 74636 KB Output is correct
82 Correct 348 ms 73084 KB Output is correct
83 Correct 543 ms 86516 KB Output is correct
84 Correct 531 ms 90608 KB Output is correct
85 Correct 491 ms 90776 KB Output is correct
86 Correct 592 ms 91380 KB Output is correct
87 Correct 535 ms 85616 KB Output is correct
88 Correct 549 ms 83696 KB Output is correct
89 Correct 610 ms 86220 KB Output is correct
90 Correct 98 ms 26624 KB Output is correct
91 Correct 357 ms 78216 KB Output is correct
92 Correct 526 ms 86788 KB Output is correct
93 Correct 553 ms 91764 KB Output is correct
94 Correct 638 ms 97152 KB Output is correct
95 Correct 673 ms 95420 KB Output is correct
96 Correct 149 ms 20488 KB Output is correct
97 Correct 2267 ms 376764 KB Output is correct
98 Correct 380 ms 37620 KB Output is correct
99 Execution timed out 5069 ms 603584 KB Time limit exceeded
100 Halted 0 ms 0 KB -