oj.uz

Submission #252735

# Submission time Handle Problem Language Result Execution time Memory
252735 2020-07-26T07:58:40 Z EntityIT New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 450916 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]);

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

  // 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 1 ms 360 KB Output is correct
2 Correct 1 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 2 ms 384 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 2 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 3 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 896 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 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 1 ms 360 KB Output is correct
2 Correct 1 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 2 ms 384 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 2 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 3 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 896 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 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 1430 ms 122644 KB Output is correct
32 Correct 70 ms 8360 KB Output is correct
33 Correct 1332 ms 118176 KB Output is correct
34 Correct 1354 ms 116080 KB Output is correct
35 Correct 1287 ms 123444 KB Output is correct
36 Correct 1268 ms 123680 KB Output is correct
37 Correct 854 ms 109960 KB Output is correct
38 Correct 872 ms 110364 KB Output is correct
39 Correct 690 ms 96608 KB Output is correct
40 Correct 717 ms 100088 KB Output is correct
41 Correct 815 ms 93452 KB Output is correct
42 Correct 889 ms 85612 KB Output is correct
43 Correct 67 ms 9384 KB Output is correct
44 Correct 763 ms 91948 KB Output is correct
45 Correct 725 ms 87444 KB Output is correct
46 Correct 607 ms 78468 KB Output is correct
47 Correct 370 ms 67996 KB Output is correct
48 Correct 425 ms 70340 KB Output is correct
49 Correct 448 ms 75932 KB Output is correct
50 Correct 475 ms 80528 KB Output is correct
51 Correct 485 ms 74888 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1942 ms 342036 KB Output is correct
2 Correct 1665 ms 330828 KB Output is correct
3 Correct 1361 ms 379392 KB Output is correct
4 Correct 1792 ms 347904 KB Output is correct
5 Correct 1784 ms 325236 KB Output is correct
6 Correct 1718 ms 325800 KB Output is correct
7 Correct 1346 ms 373940 KB Output is correct
8 Correct 1794 ms 342272 KB Output is correct
9 Correct 2092 ms 336656 KB Output is correct
10 Correct 2190 ms 331108 KB Output is correct
11 Correct 1524 ms 327604 KB Output is correct
12 Correct 1959 ms 330052 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5082 ms 450916 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 360 KB Output is correct
2 Correct 1 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 2 ms 384 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 2 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 3 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 896 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 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 1430 ms 122644 KB Output is correct
32 Correct 70 ms 8360 KB Output is correct
33 Correct 1332 ms 118176 KB Output is correct
34 Correct 1354 ms 116080 KB Output is correct
35 Correct 1287 ms 123444 KB Output is correct
36 Correct 1268 ms 123680 KB Output is correct
37 Correct 854 ms 109960 KB Output is correct
38 Correct 872 ms 110364 KB Output is correct
39 Correct 690 ms 96608 KB Output is correct
40 Correct 717 ms 100088 KB Output is correct
41 Correct 815 ms 93452 KB Output is correct
42 Correct 889 ms 85612 KB Output is correct
43 Correct 67 ms 9384 KB Output is correct
44 Correct 763 ms 91948 KB Output is correct
45 Correct 725 ms 87444 KB Output is correct
46 Correct 607 ms 78468 KB Output is correct
47 Correct 370 ms 67996 KB Output is correct
48 Correct 425 ms 70340 KB Output is correct
49 Correct 448 ms 75932 KB Output is correct
50 Correct 475 ms 80528 KB Output is correct
51 Correct 485 ms 74888 KB Output is correct
52 Correct 484 ms 77944 KB Output is correct
53 Correct 454 ms 76964 KB Output is correct
54 Correct 773 ms 87972 KB Output is correct
55 Correct 697 ms 92600 KB Output is correct
56 Correct 595 ms 93208 KB Output is correct
57 Correct 724 ms 92764 KB Output is correct
58 Correct 666 ms 87540 KB Output is correct
59 Correct 616 ms 85700 KB Output is correct
60 Correct 772 ms 87644 KB Output is correct
61 Correct 110 ms 37800 KB Output is correct
62 Correct 453 ms 81324 KB Output is correct
63 Correct 703 ms 88664 KB Output is correct
64 Correct 735 ms 93248 KB Output is correct
65 Correct 830 ms 98412 KB Output is correct
66 Correct 809 ms 96568 KB Output is correct
67 Correct 214 ms 22884 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 1 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 2 ms 384 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 3 ms 896 KB Output is correct
13 Correct 2 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 3 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 896 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 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 1430 ms 122644 KB Output is correct
32 Correct 70 ms 8360 KB Output is correct
33 Correct 1332 ms 118176 KB Output is correct
34 Correct 1354 ms 116080 KB Output is correct
35 Correct 1287 ms 123444 KB Output is correct
36 Correct 1268 ms 123680 KB Output is correct
37 Correct 854 ms 109960 KB Output is correct
38 Correct 872 ms 110364 KB Output is correct
39 Correct 690 ms 96608 KB Output is correct
40 Correct 717 ms 100088 KB Output is correct
41 Correct 815 ms 93452 KB Output is correct
42 Correct 889 ms 85612 KB Output is correct
43 Correct 67 ms 9384 KB Output is correct
44 Correct 763 ms 91948 KB Output is correct
45 Correct 725 ms 87444 KB Output is correct
46 Correct 607 ms 78468 KB Output is correct
47 Correct 370 ms 67996 KB Output is correct
48 Correct 425 ms 70340 KB Output is correct
49 Correct 448 ms 75932 KB Output is correct
50 Correct 475 ms 80528 KB Output is correct
51 Correct 485 ms 74888 KB Output is correct
52 Correct 1942 ms 342036 KB Output is correct
53 Correct 1665 ms 330828 KB Output is correct
54 Correct 1361 ms 379392 KB Output is correct
55 Correct 1792 ms 347904 KB Output is correct
56 Correct 1784 ms 325236 KB Output is correct
57 Correct 1718 ms 325800 KB Output is correct
58 Correct 1346 ms 373940 KB Output is correct
59 Correct 1794 ms 342272 KB Output is correct
60 Correct 2092 ms 336656 KB Output is correct
61 Correct 2190 ms 331108 KB Output is correct
62 Correct 1524 ms 327604 KB Output is correct
63 Correct 1959 ms 330052 KB Output is correct
64 Execution timed out 5082 ms 450916 KB Time limit exceeded
65 Halted 0 ms 0 KB -