Submission #252785

#TimeUsernameProblemLanguageResultExecution timeMemory
252785EntityITNew Home (APIO18_new_home)C++14
80 / 100
5062 ms533876 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); 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; segments[0].reserve(SZ(changes) << 1); segments[1].reserve(SZ(changes) << 1); 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, 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); if (get<2>(segments[true].back()) == get<3>(segments[true].back())) { segments[true].pop_back(); } 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); if (get<2>(segments[false].back()) == get<3>(segments[false].back())) { segments[false].pop_back(); } 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); if (get<2>(segments[false].back()) == get<3>(segments[false].back())) { segments[false].pop_back(); } 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); if (get<2>(segments[true].back()) == get<3>(segments[true].back())) { segments[true].pop_back(); } begin_times_types[true][type].erase(make_pair((a + b) >> 1, b)); } }; 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, x); Insert(x, kMaxX + 2); } else if (it == n_occurrences_xs_types[type].begin()) { Erase(0, next(it)->first); Insert(0, x); Insert(x, next(it)->first); } else if (next(it) == n_occurrences_xs_types[type].end()) { Erase(prev(it)->first, kMaxX + 2); Insert(prev(it)->first, x); Insert(x, kMaxX + 2); } else { Erase(prev(it)->first, next(it)->first); Insert(prev(it)->first, x); Insert(x, next(it)->first); } } 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, next(it)->first); } else if (next(it) == n_occurrences_xs_types[type].end()) { Erase(prev(it)->first, x); Erase(x, kMaxX + 2); Insert(prev(it)->first, kMaxX + 2); } else { Erase(prev(it)->first, x); Erase(x, next(it)->first); Insert(prev(it)->first, next(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)); } 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; it.InsertSegment(be_time, en_time, 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; it.InsertSegment(be_time, en_time, 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...