oj.uz

Submission #252739

# Submission time Handle Problem Language Result Execution time Memory
252739 2020-07-26T08:07:38 Z EntityIT New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 474288 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);
          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;
    }
    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 1 ms 292 KB Output is correct
2 Correct 1 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 3 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 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 2 ms 896 KB Output is correct
16 Correct 4 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 4 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 2 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 2 ms 896 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 1 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 1 ms 640 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 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 3 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 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 2 ms 896 KB Output is correct
16 Correct 4 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 4 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 2 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 2 ms 896 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 1 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 1 ms 640 KB Output is correct
31 Correct 1236 ms 119712 KB Output is correct
32 Correct 70 ms 7464 KB Output is correct
33 Correct 1044 ms 115580 KB Output is correct
34 Correct 993 ms 113312 KB Output is correct
35 Correct 1094 ms 120752 KB Output is correct
36 Correct 1390 ms 120880 KB Output is correct
37 Correct 770 ms 107148 KB Output is correct
38 Correct 829 ms 107420 KB Output is correct
39 Correct 646 ms 93704 KB Output is correct
40 Correct 653 ms 97264 KB Output is correct
41 Correct 668 ms 90544 KB Output is correct
42 Correct 806 ms 82916 KB Output is correct
43 Correct 66 ms 7080 KB Output is correct
44 Correct 697 ms 89336 KB Output is correct
45 Correct 855 ms 84680 KB Output is correct
46 Correct 542 ms 75640 KB Output is correct
47 Correct 336 ms 65048 KB Output is correct
48 Correct 343 ms 67652 KB Output is correct
49 Correct 409 ms 73108 KB Output is correct
50 Correct 443 ms 77712 KB Output is correct
51 Correct 395 ms 72188 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2268 ms 336116 KB Output is correct
2 Correct 1632 ms 325516 KB Output is correct
3 Correct 1434 ms 373956 KB Output is correct
4 Correct 1851 ms 342556 KB Output is correct
5 Correct 1718 ms 319936 KB Output is correct
6 Correct 1663 ms 320560 KB Output is correct
7 Correct 1374 ms 368684 KB Output is correct
8 Correct 1879 ms 337584 KB Output is correct
9 Correct 2128 ms 331740 KB Output is correct
10 Correct 2090 ms 326336 KB Output is correct
11 Correct 1511 ms 322412 KB Output is correct
12 Correct 1916 ms 325080 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4961 ms 444524 KB Output is correct
2 Correct 329 ms 40320 KB Output is correct
3 Execution timed out 5068 ms 474288 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 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 3 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 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 2 ms 896 KB Output is correct
16 Correct 4 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 4 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 2 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 2 ms 896 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 1 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 1 ms 640 KB Output is correct
31 Correct 1236 ms 119712 KB Output is correct
32 Correct 70 ms 7464 KB Output is correct
33 Correct 1044 ms 115580 KB Output is correct
34 Correct 993 ms 113312 KB Output is correct
35 Correct 1094 ms 120752 KB Output is correct
36 Correct 1390 ms 120880 KB Output is correct
37 Correct 770 ms 107148 KB Output is correct
38 Correct 829 ms 107420 KB Output is correct
39 Correct 646 ms 93704 KB Output is correct
40 Correct 653 ms 97264 KB Output is correct
41 Correct 668 ms 90544 KB Output is correct
42 Correct 806 ms 82916 KB Output is correct
43 Correct 66 ms 7080 KB Output is correct
44 Correct 697 ms 89336 KB Output is correct
45 Correct 855 ms 84680 KB Output is correct
46 Correct 542 ms 75640 KB Output is correct
47 Correct 336 ms 65048 KB Output is correct
48 Correct 343 ms 67652 KB Output is correct
49 Correct 409 ms 73108 KB Output is correct
50 Correct 443 ms 77712 KB Output is correct
51 Correct 395 ms 72188 KB Output is correct
52 Correct 414 ms 75540 KB Output is correct
53 Correct 403 ms 74792 KB Output is correct
54 Correct 641 ms 85924 KB Output is correct
55 Correct 605 ms 90452 KB Output is correct
56 Correct 539 ms 90776 KB Output is correct
57 Correct 633 ms 90672 KB Output is correct
58 Correct 641 ms 85368 KB Output is correct
59 Correct 564 ms 83496 KB Output is correct
60 Correct 632 ms 85444 KB Output is correct
61 Correct 102 ms 35496 KB Output is correct
62 Correct 467 ms 79272 KB Output is correct
63 Correct 622 ms 86180 KB Output is correct
64 Correct 632 ms 90916 KB Output is correct
65 Correct 672 ms 95992 KB Output is correct
66 Correct 801 ms 94384 KB Output is correct
67 Correct 170 ms 21432 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 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 3 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 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 2 ms 896 KB Output is correct
16 Correct 4 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 4 ms 896 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 2 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 2 ms 896 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 1 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 1 ms 640 KB Output is correct
31 Correct 1236 ms 119712 KB Output is correct
32 Correct 70 ms 7464 KB Output is correct
33 Correct 1044 ms 115580 KB Output is correct
34 Correct 993 ms 113312 KB Output is correct
35 Correct 1094 ms 120752 KB Output is correct
36 Correct 1390 ms 120880 KB Output is correct
37 Correct 770 ms 107148 KB Output is correct
38 Correct 829 ms 107420 KB Output is correct
39 Correct 646 ms 93704 KB Output is correct
40 Correct 653 ms 97264 KB Output is correct
41 Correct 668 ms 90544 KB Output is correct
42 Correct 806 ms 82916 KB Output is correct
43 Correct 66 ms 7080 KB Output is correct
44 Correct 697 ms 89336 KB Output is correct
45 Correct 855 ms 84680 KB Output is correct
46 Correct 542 ms 75640 KB Output is correct
47 Correct 336 ms 65048 KB Output is correct
48 Correct 343 ms 67652 KB Output is correct
49 Correct 409 ms 73108 KB Output is correct
50 Correct 443 ms 77712 KB Output is correct
51 Correct 395 ms 72188 KB Output is correct
52 Correct 2268 ms 336116 KB Output is correct
53 Correct 1632 ms 325516 KB Output is correct
54 Correct 1434 ms 373956 KB Output is correct
55 Correct 1851 ms 342556 KB Output is correct
56 Correct 1718 ms 319936 KB Output is correct
57 Correct 1663 ms 320560 KB Output is correct
58 Correct 1374 ms 368684 KB Output is correct
59 Correct 1879 ms 337584 KB Output is correct
60 Correct 2128 ms 331740 KB Output is correct
61 Correct 2090 ms 326336 KB Output is correct
62 Correct 1511 ms 322412 KB Output is correct
63 Correct 1916 ms 325080 KB Output is correct
64 Correct 4961 ms 444524 KB Output is correct
65 Correct 329 ms 40320 KB Output is correct
66 Execution timed out 5068 ms 474288 KB Time limit exceeded
67 Halted 0 ms 0 KB -