#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 {
struct Node {
Node* l_child,* r_child;
array<vec<pair<int, int>, 1>, 2> segments;
vec<pair<int, int>, 1> queries;
Node(Node* t_left_child, Node* t_right_child, vec<pair<int, int>, 1> t_queries)
: l_child(t_left_child),
r_child(t_right_child),
segments({}),
queries(t_queries) {}
};
Node* root;
int n;
IT(int t_n, vec<pair<int, int>, 2> queries_time_marks)
: n(t_n) {
function<Node*(int, int)> Build = [&](int l_pos, int r_pos) {
if (l_pos == r_pos) {
return new Node(nullptr, nullptr, queries_time_marks[l_pos]);
}
int m_pos = (l_pos + r_pos) >> 1;
Node* node = new Node(Build(l_pos, m_pos), Build(m_pos + 1, r_pos), vec<pair<int, int>, 1>());
merge(ALL(node->l_child->queries), ALL(node->r_child->queries), back_inserter(node->queries));
return node;
};
root = Build(0, n - 1);
}
void InsertSegment(int l, int r, bool slope, pair<int, int> val, Node* node, int l_pos, int r_pos) {
if (r < l_pos || r_pos < l) {
return;
}
if (l <= l_pos && r_pos <= r) {
node->segments[slope].emplace_back(val);
return;
}
int m_pos = (l_pos + r_pos) >> 1;
InsertSegment(l, r, slope, val, node->l_child, l_pos, m_pos);
InsertSegment(l, r, slope, val, node->r_child, m_pos + 1, r_pos);
}
void InsertSegment(int l, int r, bool slope, pair<int, int> val) {
InsertSegment(l, r, slope, val, root, 0, n - 1);
}
};
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<map<pair<int, int>, int>, 2> begin_time;
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 map<int, int> n_occurrences;
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_time[true][make_pair(2, b)] = cur_time;
} else if (b > kMaxX) {
begin_time[false][make_pair(a, kMaxX)] = cur_time;
} else {
begin_time[false][make_pair(a, (a + b) >> 1)] = begin_time[true][make_pair((a + b) >> 1, b)] = cur_time;
}
};
auto Erase = [&](int a, int b) {
if (!a) {
segments[true].emplace_back(2, b, begin_time[true][make_pair(2, b)], cur_time);
} else if (b > kMaxX) {
segments[false].emplace_back(a, kMaxX, begin_time[false][make_pair(a, kMaxX)], cur_time);
} else {
segments[false].emplace_back(a, (a + b) >> 1, begin_time[false][make_pair(a, (a + b) >> 1)], cur_time);
segments[true].emplace_back((a + b) >> 1, b, begin_time[true][make_pair((a + b) >> 1, b)], cur_time);
}
};
if (insertion) {
if ((++n_occurrences[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[x])) {
auto it = xs_types[type].find(x);
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));
}
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));
}
function<void(IT::Node*)> Solve = [&](IT::Node* node) {
if (node == nullptr) {
return;
}
int max_x = 0;
auto it_segments = node->segments[true].begin();
for (auto& query : node->queries) {
for (; it_segments != node->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 = node->segments[false].begin();
reverse(ALL(node->queries));
for (auto& query : node->queries) {
for (; it_segments != node->segments[false].end() && it_segments->second >= query.first; ++it_segments) {
Minimize(min_x, it_segments->first);
}
Maximize(answers[query.second], query.first - min_x);
}
Solve(node->l_child); Solve(node->r_child);
};
Solve(it.root);
for (auto& answer : answers) {
cout << (~answer ? answer >> 1 : -1) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5081 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5081 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1154 ms |
226944 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1232 ms |
234624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5081 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5081 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
