oj.uz

Submission #253866

# Submission time Handle Problem Language Result Execution time Memory
253866 2020-07-29T00:54:22 Z EntityIT New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 627220 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>, 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 1 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 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 768 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 3 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 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 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 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 768 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 3 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 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 951 ms 122344 KB Output is correct
32 Correct 66 ms 7688 KB Output is correct
33 Correct 838 ms 118028 KB Output is correct
34 Correct 861 ms 115884 KB Output is correct
35 Correct 894 ms 123368 KB Output is correct
36 Correct 857 ms 123492 KB Output is correct
37 Correct 627 ms 109540 KB Output is correct
38 Correct 638 ms 109688 KB Output is correct
39 Correct 517 ms 96176 KB Output is correct
40 Correct 546 ms 99592 KB Output is correct
41 Correct 633 ms 93296 KB Output is correct
42 Correct 607 ms 85620 KB Output is correct
43 Correct 66 ms 8464 KB Output is correct
44 Correct 640 ms 91636 KB Output is correct
45 Correct 598 ms 87028 KB Output is correct
46 Correct 499 ms 78068 KB Output is correct
47 Correct 331 ms 67312 KB Output is correct
48 Correct 317 ms 69920 KB Output is correct
49 Correct 401 ms 75560 KB Output is correct
50 Correct 402 ms 80240 KB Output is correct
51 Correct 395 ms 74232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1400 ms 320660 KB Output is correct
2 Correct 1240 ms 301212 KB Output is correct
3 Correct 1221 ms 357480 KB Output is correct
4 Correct 1308 ms 329364 KB Output is correct
5 Correct 1333 ms 312304 KB Output is correct
6 Correct 1257 ms 312696 KB Output is correct
7 Correct 1223 ms 357568 KB Output is correct
8 Correct 1307 ms 329244 KB Output is correct
9 Correct 1422 ms 319408 KB Output is correct
10 Correct 1482 ms 313736 KB Output is correct
11 Correct 1171 ms 310824 KB Output is correct
12 Correct 1319 ms 313012 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4142 ms 452728 KB Output is correct
2 Correct 304 ms 36836 KB Output is correct
3 Correct 3831 ms 469140 KB Output is correct
4 Correct 1561 ms 340888 KB Output is correct
5 Correct 2624 ms 366220 KB Output is correct
6 Correct 2299 ms 359964 KB Output is correct
7 Correct 3979 ms 493816 KB Output is correct
8 Correct 3843 ms 482004 KB Output is correct
9 Correct 1687 ms 376864 KB Output is correct
10 Correct 2904 ms 439736 KB Output is correct
11 Correct 3869 ms 477160 KB Output is correct
12 Correct 4014 ms 469032 KB Output is correct
13 Correct 1894 ms 381228 KB Output is correct
14 Correct 1928 ms 410504 KB Output is correct
15 Correct 2177 ms 435144 KB Output is correct
16 Correct 2530 ms 438316 KB Output is correct
17 Correct 2311 ms 413088 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 768 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 3 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 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 951 ms 122344 KB Output is correct
32 Correct 66 ms 7688 KB Output is correct
33 Correct 838 ms 118028 KB Output is correct
34 Correct 861 ms 115884 KB Output is correct
35 Correct 894 ms 123368 KB Output is correct
36 Correct 857 ms 123492 KB Output is correct
37 Correct 627 ms 109540 KB Output is correct
38 Correct 638 ms 109688 KB Output is correct
39 Correct 517 ms 96176 KB Output is correct
40 Correct 546 ms 99592 KB Output is correct
41 Correct 633 ms 93296 KB Output is correct
42 Correct 607 ms 85620 KB Output is correct
43 Correct 66 ms 8464 KB Output is correct
44 Correct 640 ms 91636 KB Output is correct
45 Correct 598 ms 87028 KB Output is correct
46 Correct 499 ms 78068 KB Output is correct
47 Correct 331 ms 67312 KB Output is correct
48 Correct 317 ms 69920 KB Output is correct
49 Correct 401 ms 75560 KB Output is correct
50 Correct 402 ms 80240 KB Output is correct
51 Correct 395 ms 74232 KB Output is correct
52 Correct 352 ms 72764 KB Output is correct
53 Correct 351 ms 71420 KB Output is correct
54 Correct 542 ms 84724 KB Output is correct
55 Correct 547 ms 88876 KB Output is correct
56 Correct 530 ms 88820 KB Output is correct
57 Correct 599 ms 89484 KB Output is correct
58 Correct 534 ms 83728 KB Output is correct
59 Correct 519 ms 81776 KB Output is correct
60 Correct 636 ms 84468 KB Output is correct
61 Correct 94 ms 24832 KB Output is correct
62 Correct 367 ms 76160 KB Output is correct
63 Correct 493 ms 85052 KB Output is correct
64 Correct 542 ms 89972 KB Output is correct
65 Correct 597 ms 95220 KB Output is correct
66 Correct 632 ms 93684 KB Output is correct
67 Correct 134 ms 19052 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 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 768 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 3 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 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 951 ms 122344 KB Output is correct
32 Correct 66 ms 7688 KB Output is correct
33 Correct 838 ms 118028 KB Output is correct
34 Correct 861 ms 115884 KB Output is correct
35 Correct 894 ms 123368 KB Output is correct
36 Correct 857 ms 123492 KB Output is correct
37 Correct 627 ms 109540 KB Output is correct
38 Correct 638 ms 109688 KB Output is correct
39 Correct 517 ms 96176 KB Output is correct
40 Correct 546 ms 99592 KB Output is correct
41 Correct 633 ms 93296 KB Output is correct
42 Correct 607 ms 85620 KB Output is correct
43 Correct 66 ms 8464 KB Output is correct
44 Correct 640 ms 91636 KB Output is correct
45 Correct 598 ms 87028 KB Output is correct
46 Correct 499 ms 78068 KB Output is correct
47 Correct 331 ms 67312 KB Output is correct
48 Correct 317 ms 69920 KB Output is correct
49 Correct 401 ms 75560 KB Output is correct
50 Correct 402 ms 80240 KB Output is correct
51 Correct 395 ms 74232 KB Output is correct
52 Correct 1400 ms 320660 KB Output is correct
53 Correct 1240 ms 301212 KB Output is correct
54 Correct 1221 ms 357480 KB Output is correct
55 Correct 1308 ms 329364 KB Output is correct
56 Correct 1333 ms 312304 KB Output is correct
57 Correct 1257 ms 312696 KB Output is correct
58 Correct 1223 ms 357568 KB Output is correct
59 Correct 1307 ms 329244 KB Output is correct
60 Correct 1422 ms 319408 KB Output is correct
61 Correct 1482 ms 313736 KB Output is correct
62 Correct 1171 ms 310824 KB Output is correct
63 Correct 1319 ms 313012 KB Output is correct
64 Correct 4142 ms 452728 KB Output is correct
65 Correct 304 ms 36836 KB Output is correct
66 Correct 3831 ms 469140 KB Output is correct
67 Correct 1561 ms 340888 KB Output is correct
68 Correct 2624 ms 366220 KB Output is correct
69 Correct 2299 ms 359964 KB Output is correct
70 Correct 3979 ms 493816 KB Output is correct
71 Correct 3843 ms 482004 KB Output is correct
72 Correct 1687 ms 376864 KB Output is correct
73 Correct 2904 ms 439736 KB Output is correct
74 Correct 3869 ms 477160 KB Output is correct
75 Correct 4014 ms 469032 KB Output is correct
76 Correct 1894 ms 381228 KB Output is correct
77 Correct 1928 ms 410504 KB Output is correct
78 Correct 2177 ms 435144 KB Output is correct
79 Correct 2530 ms 438316 KB Output is correct
80 Correct 2311 ms 413088 KB Output is correct
81 Correct 352 ms 72764 KB Output is correct
82 Correct 351 ms 71420 KB Output is correct
83 Correct 542 ms 84724 KB Output is correct
84 Correct 547 ms 88876 KB Output is correct
85 Correct 530 ms 88820 KB Output is correct
86 Correct 599 ms 89484 KB Output is correct
87 Correct 534 ms 83728 KB Output is correct
88 Correct 519 ms 81776 KB Output is correct
89 Correct 636 ms 84468 KB Output is correct
90 Correct 94 ms 24832 KB Output is correct
91 Correct 367 ms 76160 KB Output is correct
92 Correct 493 ms 85052 KB Output is correct
93 Correct 542 ms 89972 KB Output is correct
94 Correct 597 ms 95220 KB Output is correct
95 Correct 632 ms 93684 KB Output is correct
96 Correct 134 ms 19052 KB Output is correct
97 Correct 2223 ms 388364 KB Output is correct
98 Correct 327 ms 39268 KB Output is correct
99 Execution timed out 5076 ms 627220 KB Time limit exceeded
100 Halted 0 ms 0 KB -