oj.uz

Submission #253867

# Submission time Handle Problem Language Result Execution time Memory
253867 2020-07-29T00:58:58 Z EntityIT New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 580956 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) {
      nodes[i].queries.reserve(SZ(nodes[i << 1].queries) + SZ(nodes[i << 1 | 1].queries));
      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>, 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);
    changes.emplace_back(r + 1, -x, type);
    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), [&](const auto& i, const auto& 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; tie(cur_time, x, type) = *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) {
        int pre_time;
        if (!a) {
          if ((pre_time = begin_times_types[type][0]) < cur_time) {
            segments[true].emplace_back(2, b, pre_time, cur_time);
          }
        } else if (b > kMaxX) {
          if ((pre_time = begin_times_types[type][a]) < cur_time) {
            segments[false].emplace_back(a, kMaxX, pre_time, cur_time);
          }
        } else {
          if ((pre_time = begin_times_types[type][a]) < cur_time) {
            segments[false].emplace_back(a, (a + b) >> 1, pre_time, cur_time);
            segments[true].emplace_back((a + b) >> 1, b, pre_time, cur_time);
          }
        }
      };

      if (x > 0) {
        auto it = n_occurrences_xs_types[type].find(x);
        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 {
        x = -x;
        auto it = n_occurrences_xs_types[type].find(x);
        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]), [&](const auto& i, const 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 1 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 2 ms 768 KB Output is correct
12 Correct 2 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 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 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 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 1 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 2 ms 768 KB Output is correct
12 Correct 2 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 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 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 2 ms 640 KB Output is correct
31 Correct 949 ms 117620 KB Output is correct
32 Correct 65 ms 6668 KB Output is correct
33 Correct 814 ms 113612 KB Output is correct
34 Correct 820 ms 111456 KB Output is correct
35 Correct 1014 ms 118720 KB Output is correct
36 Correct 955 ms 118764 KB Output is correct
37 Correct 657 ms 104808 KB Output is correct
38 Correct 614 ms 105388 KB Output is correct
39 Correct 492 ms 91636 KB Output is correct
40 Correct 553 ms 95196 KB Output is correct
41 Correct 620 ms 88132 KB Output is correct
42 Correct 691 ms 81576 KB Output is correct
43 Correct 66 ms 6536 KB Output is correct
44 Correct 712 ms 87256 KB Output is correct
45 Correct 610 ms 82160 KB Output is correct
46 Correct 478 ms 73200 KB Output is correct
47 Correct 333 ms 63732 KB Output is correct
48 Correct 330 ms 65144 KB Output is correct
49 Correct 389 ms 71244 KB Output is correct
50 Correct 430 ms 76276 KB Output is correct
51 Correct 400 ms 70012 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1478 ms 305252 KB Output is correct
2 Correct 1273 ms 295500 KB Output is correct
3 Correct 1276 ms 338684 KB Output is correct
4 Correct 1377 ms 310812 KB Output is correct
5 Correct 1339 ms 294708 KB Output is correct
6 Correct 1220 ms 295276 KB Output is correct
7 Correct 1279 ms 338924 KB Output is correct
8 Correct 1420 ms 310604 KB Output is correct
9 Correct 1830 ms 300692 KB Output is correct
10 Correct 1470 ms 295912 KB Output is correct
11 Correct 1153 ms 293708 KB Output is correct
12 Correct 1313 ms 295448 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4498 ms 431276 KB Output is correct
2 Correct 292 ms 30820 KB Output is correct
3 Correct 3674 ms 447144 KB Output is correct
4 Correct 1733 ms 328684 KB Output is correct
5 Correct 2682 ms 354024 KB Output is correct
6 Correct 2353 ms 348408 KB Output is correct
7 Correct 3827 ms 472000 KB Output is correct
8 Correct 3752 ms 460092 KB Output is correct
9 Correct 1689 ms 360808 KB Output is correct
10 Correct 2780 ms 421864 KB Output is correct
11 Correct 3880 ms 458160 KB Output is correct
12 Correct 3920 ms 446752 KB Output is correct
13 Correct 1818 ms 357792 KB Output is correct
14 Correct 1832 ms 386464 KB Output is correct
15 Correct 2130 ms 412064 KB Output is correct
16 Correct 2463 ms 417588 KB Output is correct
17 Correct 2344 ms 389728 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 1 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 2 ms 768 KB Output is correct
12 Correct 2 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 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 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 2 ms 640 KB Output is correct
31 Correct 949 ms 117620 KB Output is correct
32 Correct 65 ms 6668 KB Output is correct
33 Correct 814 ms 113612 KB Output is correct
34 Correct 820 ms 111456 KB Output is correct
35 Correct 1014 ms 118720 KB Output is correct
36 Correct 955 ms 118764 KB Output is correct
37 Correct 657 ms 104808 KB Output is correct
38 Correct 614 ms 105388 KB Output is correct
39 Correct 492 ms 91636 KB Output is correct
40 Correct 553 ms 95196 KB Output is correct
41 Correct 620 ms 88132 KB Output is correct
42 Correct 691 ms 81576 KB Output is correct
43 Correct 66 ms 6536 KB Output is correct
44 Correct 712 ms 87256 KB Output is correct
45 Correct 610 ms 82160 KB Output is correct
46 Correct 478 ms 73200 KB Output is correct
47 Correct 333 ms 63732 KB Output is correct
48 Correct 330 ms 65144 KB Output is correct
49 Correct 389 ms 71244 KB Output is correct
50 Correct 430 ms 76276 KB Output is correct
51 Correct 400 ms 70012 KB Output is correct
52 Correct 383 ms 73088 KB Output is correct
53 Correct 413 ms 71676 KB Output is correct
54 Correct 664 ms 84976 KB Output is correct
55 Correct 620 ms 87540 KB Output is correct
56 Correct 570 ms 87284 KB Output is correct
57 Correct 604 ms 87924 KB Output is correct
58 Correct 535 ms 83188 KB Output is correct
59 Correct 492 ms 81136 KB Output is correct
60 Correct 606 ms 83572 KB Output is correct
61 Correct 97 ms 24832 KB Output is correct
62 Correct 387 ms 76288 KB Output is correct
63 Correct 569 ms 84468 KB Output is correct
64 Correct 539 ms 88976 KB Output is correct
65 Correct 616 ms 93660 KB Output is correct
66 Correct 632 ms 91636 KB Output is correct
67 Correct 134 ms 19060 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 1 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 2 ms 768 KB Output is correct
12 Correct 2 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 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 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 2 ms 640 KB Output is correct
31 Correct 949 ms 117620 KB Output is correct
32 Correct 65 ms 6668 KB Output is correct
33 Correct 814 ms 113612 KB Output is correct
34 Correct 820 ms 111456 KB Output is correct
35 Correct 1014 ms 118720 KB Output is correct
36 Correct 955 ms 118764 KB Output is correct
37 Correct 657 ms 104808 KB Output is correct
38 Correct 614 ms 105388 KB Output is correct
39 Correct 492 ms 91636 KB Output is correct
40 Correct 553 ms 95196 KB Output is correct
41 Correct 620 ms 88132 KB Output is correct
42 Correct 691 ms 81576 KB Output is correct
43 Correct 66 ms 6536 KB Output is correct
44 Correct 712 ms 87256 KB Output is correct
45 Correct 610 ms 82160 KB Output is correct
46 Correct 478 ms 73200 KB Output is correct
47 Correct 333 ms 63732 KB Output is correct
48 Correct 330 ms 65144 KB Output is correct
49 Correct 389 ms 71244 KB Output is correct
50 Correct 430 ms 76276 KB Output is correct
51 Correct 400 ms 70012 KB Output is correct
52 Correct 1478 ms 305252 KB Output is correct
53 Correct 1273 ms 295500 KB Output is correct
54 Correct 1276 ms 338684 KB Output is correct
55 Correct 1377 ms 310812 KB Output is correct
56 Correct 1339 ms 294708 KB Output is correct
57 Correct 1220 ms 295276 KB Output is correct
58 Correct 1279 ms 338924 KB Output is correct
59 Correct 1420 ms 310604 KB Output is correct
60 Correct 1830 ms 300692 KB Output is correct
61 Correct 1470 ms 295912 KB Output is correct
62 Correct 1153 ms 293708 KB Output is correct
63 Correct 1313 ms 295448 KB Output is correct
64 Correct 4498 ms 431276 KB Output is correct
65 Correct 292 ms 30820 KB Output is correct
66 Correct 3674 ms 447144 KB Output is correct
67 Correct 1733 ms 328684 KB Output is correct
68 Correct 2682 ms 354024 KB Output is correct
69 Correct 2353 ms 348408 KB Output is correct
70 Correct 3827 ms 472000 KB Output is correct
71 Correct 3752 ms 460092 KB Output is correct
72 Correct 1689 ms 360808 KB Output is correct
73 Correct 2780 ms 421864 KB Output is correct
74 Correct 3880 ms 458160 KB Output is correct
75 Correct 3920 ms 446752 KB Output is correct
76 Correct 1818 ms 357792 KB Output is correct
77 Correct 1832 ms 386464 KB Output is correct
78 Correct 2130 ms 412064 KB Output is correct
79 Correct 2463 ms 417588 KB Output is correct
80 Correct 2344 ms 389728 KB Output is correct
81 Correct 383 ms 73088 KB Output is correct
82 Correct 413 ms 71676 KB Output is correct
83 Correct 664 ms 84976 KB Output is correct
84 Correct 620 ms 87540 KB Output is correct
85 Correct 570 ms 87284 KB Output is correct
86 Correct 604 ms 87924 KB Output is correct
87 Correct 535 ms 83188 KB Output is correct
88 Correct 492 ms 81136 KB Output is correct
89 Correct 606 ms 83572 KB Output is correct
90 Correct 97 ms 24832 KB Output is correct
91 Correct 387 ms 76288 KB Output is correct
92 Correct 569 ms 84468 KB Output is correct
93 Correct 539 ms 88976 KB Output is correct
94 Correct 616 ms 93660 KB Output is correct
95 Correct 632 ms 91636 KB Output is correct
96 Correct 134 ms 19060 KB Output is correct
97 Correct 2256 ms 373864 KB Output is correct
98 Correct 336 ms 32612 KB Output is correct
99 Execution timed out 5139 ms 580956 KB Time limit exceeded
100 Halted 0 ms 0 KB -