Submission #252968

#TimeUsernameProblemLanguageResultExecution timeMemory
252968EntityITNew Home (APIO18_new_home)C++14
80 / 100
5069 ms617980 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 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, bool>, 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, 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); 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; bool insertion; tie(cur_time, x, type, insertion) = *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); } } }; auto it = n_occurrences_xs_types[type].find(x); if (insertion) { 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 { 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]), [&](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; 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; }
#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...