#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
int n, k, q;
vector <int> s[N];
int ans[N];
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
int x, t, a, b;
cin >> x >> t >> a >> b;
s[t].push_back(x);
}
vector <pair <int, int> > work;
vector <tuple <int, int, int, int> > events;
for (int i = 1; i <= q; ++i) {
int x, y;
cin >> x >> y;
work.push_back({x * 2, i});
}
auto add_line = [&](int x, int y, int a, int b) {
// cout << x << ' ' << y << ' ' << a << ' ' << b << "aaaaa\n";
events.push_back({x, -1, a, b});
events.push_back({y, 1, a, b});
};
for (int i = 1; i <= k; ++i) {
int last = - 1e9;
add_line(- 1e9, s[i].front() * 2, - 1, s[i].front());
for (int j = 0; j + 1 < s[i].size(); ++j) {
add_line(s[i][j] * 2, s[i][j] + s[i][j + 1], 1, - s[i][j]);
add_line(s[i][j] + s[i][j + 1], s[i][j + 1] * 2, - 1, s[i][j + 1]);
}
add_line(s[i].back() * 2, 1e9, 1, - s[i].back());
}
sort(events.begin(), events.end());
sort(work.begin(), work.end());
int i = 0;
multiset <int> lft, rgt;
for (auto [x, id]: work) {
while (i < events.size() && get<0>(events[i]) <= x) {
auto [_, cmd, a, b] = events[i];
if (cmd == -1) {
if (a < 0) lft.insert(b);
else rgt.insert(b);
} else {
if (a < 0) lft.erase(lft.find(b));
else rgt.erase(rgt.find(b));
}
++i;
}
x /= 2;
ans[id] = 0;
if (rgt.size()) ans[id] = max(ans[id], x + *(--rgt.end()));
if (lft.size()) ans[id] = max(ans[id], - x + *(--lft.end()));
}
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 0; j + 1 < s[i].size(); ++j) {
| ~~~~~~^~~~~~~~~~~~~
new_home.cpp:40:13: warning: unused variable 'last' [-Wunused-variable]
40 | int last = - 1e9;
| ^~~~
new_home.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
52 | for (auto [x, id]: work) {
| ^
new_home.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (i < events.size() && get<0>(events[i]) <= x) {
| ~~^~~~~~~~~~~~~~~
new_home.cpp:54:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto [_, cmd, a, b] = events[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
14800 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
14800 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
455 ms |
81684 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
405 ms |
74308 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
14800 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
14800 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
