oj.uz

Submission #252744

# Submission time Handle Problem Language Result Execution time Memory
252744 2020-07-26T08:13:18 Z EntityIT New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 457836 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 l, int r, bool slope, pair<int, int> val) {
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        nodes[l++].segments[slope].emplace_back(val);
      }
      if (r & 1) {
        nodes[--r].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;

  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]);
      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;
    if (be_time == en_time) {
      continue;
    }
    it.InsertSegment(be_time, en_time - 1, 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;
    if (be_time == en_time) {
      continue;
    }
    it.InsertSegment(be_time, en_time - 1, 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 0 ms 384 KB Output is correct
4 Correct 0 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 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 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 2 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 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 2 ms 768 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 0 ms 384 KB Output is correct
4 Correct 0 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 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 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 2 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 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 2 ms 768 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 1064 ms 119708 KB Output is correct
32 Correct 65 ms 7464 KB Output is correct
33 Correct 1018 ms 115488 KB Output is correct
34 Correct 984 ms 113224 KB Output is correct
35 Correct 1164 ms 120868 KB Output is correct
36 Correct 1124 ms 120820 KB Output is correct
37 Correct 733 ms 107012 KB Output is correct
38 Correct 764 ms 107472 KB Output is correct
39 Correct 611 ms 93840 KB Output is correct
40 Correct 655 ms 97272 KB Output is correct
41 Correct 661 ms 90632 KB Output is correct
42 Correct 615 ms 83148 KB Output is correct
43 Correct 65 ms 7080 KB Output is correct
44 Correct 683 ms 89152 KB Output is correct
45 Correct 674 ms 84760 KB Output is correct
46 Correct 534 ms 75764 KB Output is correct
47 Correct 340 ms 65052 KB Output is correct
48 Correct 341 ms 67548 KB Output is correct
49 Correct 412 ms 73116 KB Output is correct
50 Correct 466 ms 77828 KB Output is correct
51 Correct 427 ms 72316 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1876 ms 328580 KB Output is correct
2 Correct 1587 ms 316292 KB Output is correct
3 Correct 1415 ms 374012 KB Output is correct
4 Correct 1777 ms 336488 KB Output is correct
5 Correct 1735 ms 316032 KB Output is correct
6 Correct 1528 ms 316360 KB Output is correct
7 Correct 1439 ms 368764 KB Output is correct
8 Correct 1815 ms 336256 KB Output is correct
9 Correct 2110 ms 323064 KB Output is correct
10 Correct 2243 ms 312100 KB Output is correct
11 Correct 1523 ms 313728 KB Output is correct
12 Correct 1936 ms 316176 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4910 ms 440424 KB Output is correct
2 Correct 312 ms 36224 KB Output is correct
3 Execution timed out 5072 ms 457836 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 0 ms 384 KB Output is correct
4 Correct 0 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 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 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 2 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 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 2 ms 768 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 1064 ms 119708 KB Output is correct
32 Correct 65 ms 7464 KB Output is correct
33 Correct 1018 ms 115488 KB Output is correct
34 Correct 984 ms 113224 KB Output is correct
35 Correct 1164 ms 120868 KB Output is correct
36 Correct 1124 ms 120820 KB Output is correct
37 Correct 733 ms 107012 KB Output is correct
38 Correct 764 ms 107472 KB Output is correct
39 Correct 611 ms 93840 KB Output is correct
40 Correct 655 ms 97272 KB Output is correct
41 Correct 661 ms 90632 KB Output is correct
42 Correct 615 ms 83148 KB Output is correct
43 Correct 65 ms 7080 KB Output is correct
44 Correct 683 ms 89152 KB Output is correct
45 Correct 674 ms 84760 KB Output is correct
46 Correct 534 ms 75764 KB Output is correct
47 Correct 340 ms 65052 KB Output is correct
48 Correct 341 ms 67548 KB Output is correct
49 Correct 412 ms 73116 KB Output is correct
50 Correct 466 ms 77828 KB Output is correct
51 Correct 427 ms 72316 KB Output is correct
52 Correct 566 ms 75820 KB Output is correct
53 Correct 410 ms 74812 KB Output is correct
54 Correct 654 ms 86000 KB Output is correct
55 Correct 767 ms 90316 KB Output is correct
56 Correct 645 ms 91036 KB Output is correct
57 Correct 677 ms 90808 KB Output is correct
58 Correct 635 ms 85500 KB Output is correct
59 Correct 573 ms 83608 KB Output is correct
60 Correct 712 ms 85668 KB Output is correct
61 Correct 107 ms 35752 KB Output is correct
62 Correct 431 ms 79400 KB Output is correct
63 Correct 596 ms 86432 KB Output is correct
64 Correct 640 ms 91052 KB Output is correct
65 Correct 682 ms 96264 KB Output is correct
66 Correct 750 ms 94412 KB Output is correct
67 Correct 189 ms 21360 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 0 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 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 896 KB Output is correct
11 Correct 3 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 2 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 3 ms 896 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 896 KB Output is correct
24 Correct 3 ms 896 KB Output is correct
25 Correct 3 ms 896 KB Output is correct
26 Correct 2 ms 768 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 1064 ms 119708 KB Output is correct
32 Correct 65 ms 7464 KB Output is correct
33 Correct 1018 ms 115488 KB Output is correct
34 Correct 984 ms 113224 KB Output is correct
35 Correct 1164 ms 120868 KB Output is correct
36 Correct 1124 ms 120820 KB Output is correct
37 Correct 733 ms 107012 KB Output is correct
38 Correct 764 ms 107472 KB Output is correct
39 Correct 611 ms 93840 KB Output is correct
40 Correct 655 ms 97272 KB Output is correct
41 Correct 661 ms 90632 KB Output is correct
42 Correct 615 ms 83148 KB Output is correct
43 Correct 65 ms 7080 KB Output is correct
44 Correct 683 ms 89152 KB Output is correct
45 Correct 674 ms 84760 KB Output is correct
46 Correct 534 ms 75764 KB Output is correct
47 Correct 340 ms 65052 KB Output is correct
48 Correct 341 ms 67548 KB Output is correct
49 Correct 412 ms 73116 KB Output is correct
50 Correct 466 ms 77828 KB Output is correct
51 Correct 427 ms 72316 KB Output is correct
52 Correct 1876 ms 328580 KB Output is correct
53 Correct 1587 ms 316292 KB Output is correct
54 Correct 1415 ms 374012 KB Output is correct
55 Correct 1777 ms 336488 KB Output is correct
56 Correct 1735 ms 316032 KB Output is correct
57 Correct 1528 ms 316360 KB Output is correct
58 Correct 1439 ms 368764 KB Output is correct
59 Correct 1815 ms 336256 KB Output is correct
60 Correct 2110 ms 323064 KB Output is correct
61 Correct 2243 ms 312100 KB Output is correct
62 Correct 1523 ms 313728 KB Output is correct
63 Correct 1936 ms 316176 KB Output is correct
64 Correct 4910 ms 440424 KB Output is correct
65 Correct 312 ms 36224 KB Output is correct
66 Execution timed out 5072 ms 457836 KB Time limit exceeded
67 Halted 0 ms 0 KB -