Submission #252735

#TimeUsernameProblemLanguageResultExecution timeMemory
252735EntityITNew Home (APIO18_new_home)C++14
57 / 100
5082 ms450916 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...