/*
APIO 2018 New Home
- Consider the case where all stores are always active
- We basically want the maximum of a bunch of "broken absolute value" graphs
- Consider the positive and negative slopes separately
- If we do this, then we get a bunch of line segments
- WLOG, extend the line segments into rays that go below the x-axis
- Since all slopes are equal, we only need to store the x-intersect of each ray
- Queries thus become prefix maximum queries (i.e. maximum ray that starts
before the queried position)
- We can handle this using a simple segment tree
- To handle the general case, notice that there are O(N) possible rays, each
with a period of relevance
- We can thus create a second segment tree indexed on time, where each leaf
is a query, and DFS on that tree to update our first segment tree
- We can avoid an additional log N factor by keeping an array of sets that
store "hidden" values at each point
- Complexity: O(N log N)
*/
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1e8;
vector<int> c_loc, c_time;
map<int, vector<pair<int, int>>> queries, toggle, ins, del;
vector<tuple<int, int, int>> stores[300001];
int ans[300001], segtree[1200001];
multiset<int> rays[300001];
int query(int loc, int node = 1, int l = 0, int r = c_loc.size() - 1) {
if (r <= loc) return segtree[node];
if (l > loc) return -1;
int mid = (l + r) / 2;
return max(query(loc, node * 2, l, mid),
query(loc, node * 2 + 1, mid + 1, r));
}
void update(int loc, int val, int node = 1, int l = 0,
int r = c_loc.size() - 1) {
if (l == r)
segtree[node] = val;
else {
int mid = (l + r) / 2;
if (loc > mid)
update(loc, val, node * 2 + 1, mid + 1, r);
else
update(loc, val, node * 2, l, mid);
}
}
void ins_ray(int loc, int val) {
if (loc == c_loc.size()) return;
// cout << "INS " << loc << ' ' << val << ' ' << rays[loc].size() << endl;
rays[loc].insert(val);
update(loc, *rays[loc].rbegin());
}
void del_ray(int loc, int val) {
if (loc == c_loc.size()) return;
// cout << "DEL " << loc << ' ' << val << ' ' << rays[loc].size() << endl;
rays[loc].erase(rays[loc].find(val));
update(loc, *rays[loc].rbegin());
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k, q;
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
int loc, type, a, b;
cin >> loc >> type >> a >> b;
stores[type].push_back({a, loc, 0});
stores[type].push_back({b + 1, loc, 1});
}
for (int i = 1; i <= q; i++) {
int loc, time;
cin >> loc >> time;
c_loc.push_back(2 * loc);
c_time.push_back(time);
queries[time].push_back({i, loc});
ans[i] = -1;
}
sort(c_loc.begin(), c_loc.end());
c_loc.erase(unique(c_loc.begin(), c_loc.end()), c_loc.end());
sort(c_time.begin(), c_time.end());
c_time.erase(unique(c_time.begin(), c_time.end()), c_time.end());
c_time.push_back(INF);
for (int _ : {0, 1}) {
for (int i = 0; i < c_loc.size(); i++) {
rays[i].clear();
rays[i].insert(-INF);
}
for (int t = 1; t <= k; t++) {
sort(stores[t].begin(), stores[t].end());
map<int, int> active, ray_at;
for (auto i : stores[t]) {
int time, loc, close;
tie(time, loc, close) = i;
time = *lower_bound(c_time.begin(), c_time.end(), time);
if (close) {
active[loc]--;
if (!active[loc]) {
active.erase(loc);
auto ub = active.upper_bound(loc);
del[time].push_back({ray_at[loc], loc});
ray_at.erase(loc);
if (ub != active.end())
del[time].push_back({ray_at[ub->first], ub->first});
if (ub != active.begin()) {
ins[time].push_back(
{prev(ub)->first + ub->first, ub->first});
ray_at[ub->first] = prev(ub)->first + ub->first;
} else if (ub != active.end()) {
ins[time].push_back({0, ub->first});
ray_at[ub->first] = 0;
}
}
} else {
if (!active[loc]) {
auto ub = active.upper_bound(loc);
if (ub != active.end()) {
del[time].push_back({ray_at[ub->first], ub->first});
ins[time].push_back({ub->first + loc, ub->first});
ray_at[ub->first] = ub->first + loc;
}
if (ub != active.begin()) {
ins[time].push_back({loc + prev(ub)->first, loc});
ray_at[loc] = loc + prev(ub)->first;
} else {
ins[time].push_back({0, loc});
ray_at[loc] = 0;
}
}
active[loc]++;
}
toggle[time].push_back({t, 1 - 2 * close});
}
}
// cout << "=== c_loc ===\n";
// for (int i : c_loc) cout << i << ' ';
// cout << endl;
// cout << "=== INSERT ===\n";
// for (auto& i : ins) {
// cout << i.first << ": ";
// for (auto& j : i.second)
// cout << '(' << j.first << ", " << j.second << ") ";
// cout << endl;
// }
// cout << "=== DELETE ===\n";
// for (auto& i : del) {
// cout << i.first << ": ";
// for (auto& j : i.second)
// cout << '(' << j.first << ", " << j.second << ") ";
// cout << endl;
// }
// cout << "=== TOGGLE ===\n";
// for (auto& i : toggle) {
// cout << i.first << ": ";
// for (auto& j : i.second)
// cout << '(' << j.first << ", " << j.second << ") ";
// cout << endl;
// }
// cout << "=== QUERIES ===\n";
// for (auto& i : queries) {
// cout << i.first << ": ";
// for (auto& j : i.second)
// cout << '(' << j.first << ", " << j.second << ") ";
// cout << endl;
// }
map<int, int> active;
fill_n(segtree + 1, 4 * c_loc.size(), -INF);
for (int t : c_time) {
for (pair<int, int> i : ins[t])
ins_ray(lower_bound(c_loc.begin(), c_loc.end(), i.first) -
c_loc.begin(),
i.second);
for (pair<int, int> i : del[t])
del_ray(lower_bound(c_loc.begin(), c_loc.end(), i.first) -
c_loc.begin(),
i.second);
for (pair<int, int> i : toggle[t]) {
active[i.first] += i.second;
if (!active[i.first]) active.erase(i.first);
}
if (active.size() == k) {
for (pair<int, int> i : queries[t]) {
int res = query(
lower_bound(c_loc.begin(), c_loc.end(), 2 * i.second) -
c_loc.begin());
if (res > 0)
ans[i.first] = max(ans[i.first], i.second - res);
// cout << "QUERY " << res << endl;
}
}
}
for (int i = 1; i <= k; i++)
for (auto& j : stores[i]) get<1>(j) = INF + 1 - get<1>(j);
for (auto& i : queries)
for (auto& j : i.second) j.second = INF + 1 - j.second;
for (auto& i : c_loc) i = 2 * INF + 2 - i;
reverse(c_loc.begin(), c_loc.end());
toggle.clear(), ins.clear();
del.clear();
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/
Compilation message
new_home.cpp: In function 'void ins_ray(int, int)':
new_home.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (loc == c_loc.size()) return;
| ~~~~^~~~~~~~~~~~~~~
new_home.cpp: In function 'void del_ray(int, int)':
new_home.cpp:62:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if (loc == c_loc.size()) return;
| ~~~~^~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:93:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < c_loc.size(); i++) {
| ~~^~~~~~~~~~~~~~
new_home.cpp:192:31: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
192 | if (active.size() == k) {
| ~~~~~~~~~~~~~~^~~~
new_home.cpp:92:14: warning: unused variable '_' [-Wunused-variable]
92 | for (int _ : {0, 1}) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21580 KB |
Output is correct |
| 2 |
Correct |
15 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21448 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
21484 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21580 KB |
Output is correct |
| 2 |
Correct |
15 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21448 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
21484 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3741 ms |
222384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
197388 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21580 KB |
Output is correct |
| 2 |
Correct |
15 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21448 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
21484 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21580 KB |
Output is correct |
| 2 |
Correct |
15 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
21448 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
21484 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
