#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10, inf = 1e9;
struct store
{
int x, t, a, b;
}s[maxn];
struct query
{
int l, y, idx;
}task[maxn];
int n, k, q;
void input()
{
cin >> n >> k >> q;
for (int i = 1; i <= n; i ++)
cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;
for (int i = 1; i <= q; i ++)
cin >> task[i].l >> task[i].y, task[i].idx = i;
}
unordered_map < int, int > rev;
int dif;
void compress_data()
{
vector < int > cor;
for (int i = 1; i <= n; i ++)
cor.push_back(s[i].x);
for (int i = 1; i <= q; i ++)
cor.push_back(task[i].l);
sort(cor.begin(), cor.end());
int sz = cor.size();
for (int i = 0; i < sz - 1; i ++)
{
cor.push_back((cor[i + 1] - cor[i]) / 2);
}
for (int i = 0; i < cor.size(); i ++)
{
if (i != 0 || cor[i - 1] != cor[i])
{
dif ++;
rev[cor[i]] = dif;
}
}
}
int type[maxn];
int solve_naive(int pivot, int year)
{
for (int i = 1; i <= k; i ++)
type[i] = inf;
for (int i = 1; i <= n; i ++)
{
if (s[i].a <= year && s[i].b >= year)
type[s[i].t] = min(type[s[i].t], abs(pivot - s[i].x));
}
int ans = -1;
for (int i = 1; i <= k; i ++)
{
if (type[i] == inf)
return -1;
ans = max(ans, type[i]);
}
return ans;
}
bool cmp_query(query t1, query t2)
{
return t1.y < t2.y;
}
struct event
{
int type, cor, add, arrive;
event(int _type, int _cor, int _add, int _arrive)
{
type = _type;
cor = _cor;
add = _add;
arrive = _arrive;
}
};
bool cmp_event(event e1, event e2)
{
if (e1.arrive != e2.arrive)
return e1.arrive < e2.arrive;
if (e1.add != e2.add)
return e1.add < e2.add;
return e1.cor < e2.cor; /// could have dublicates
}
multiset < int > tree[4 * maxn];
void apply_update(int root, pair < int, int > val)
{
if (val.first == -1)
{
tree[root].erase(tree[root].find(val.second));
}
else
{
tree[root].insert(val.second);
}
}
void update(int root, int left, int right, int qleft, int qright, pair < int, int > val)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
apply_update(root, val);
return;
}
int mid = (left + right) / 2;
update(root * 2, left, mid, qleft, qright, val);
update(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
int query(int root, int left, int right, int pos, int cor)
{
int far = 0;
if (!tree[root].empty())
{
far = max(far, abs(cor - *tree[root].begin()));
far = max(far, abs(cor - *tree[root].rbegin()));
}
if (left != right)
{
int mid = (left + right) / 2;
if (pos <= mid)
far = max(far, query(root * 2, left, mid, pos, cor));
else
far = max(far, query(root * 2 + 1, mid + 1, right, pos, cor));
}
return far;
}
multiset < int > act[maxn];
void add_event(int type, int cor)
{
multiset < int > :: iterator it = act[type].upper_bound(cor);
int aft = *it;
int bef = *prev(it);
if (bef == -inf && aft == inf)
{
update(1, 1, dif, 1, dif, {-1, -inf});
update(1, 1, dif, 1, rev[cor], {1, cor});
update(1, 1, dif, rev[cor], dif, {1, cor});
}
else
if (bef == - inf) // aft != inf
{
update(1, 1, dif, 1, rev[aft], {-1, aft});
update(1, 1, dif, 1, rev[cor], {1, cor});
int mid = (cor + aft) / 2;
update(1, 1, dif, rev[cor], rev[mid], {1, cor});
update(1, 1, dif, rev[mid] + 1, rev[aft], {1, aft});
}
else
if (aft == inf) // bef != inf
{
update(1, 1, dif, rev[bef], dif, {-1, bef});
update(1, 1, dif, rev[cor], dif, {1, cor});
int mid = (bef + cor) / 2;
update(1, 1, dif, rev[bef], rev[mid], {1, bef});
update(1, 1, dif, rev[mid] + 1, rev[cor], {1, cor});
}
else /// aft != inf && bef != inf
{
int mid = (bef + aft) / 2;
update(1, 1, dif, rev[bef], rev[mid], {-1, bef});
update(1, 1, dif, rev[mid] + 1, rev[aft], {-1, aft});
int mid_left = (bef + cor) / 2;
update(1, 1, dif, rev[bef], rev[mid_left], {1, bef});
update(1, 1, dif, rev[mid_left] + 1, rev[cor], {1, cor});
int mid_right = (cor + aft) / 2;
update(1, 1, dif, rev[cor], rev[mid_right], {1, cor});
update(1, 1, dif, rev[mid_right] + 1, rev[aft], {1, aft});
}
act[type].insert(cor);
}
void remove_event(int type, int cor)
{
multiset < int > :: iterator it = act[type].find(cor);
int aft = *next(it);
int bef = *prev(it);
if (bef == -inf && aft == inf)
{
update(1, 1, dif, 1, dif, {+1, -inf});
update(1, 1, dif, 1, rev[cor], {-1, cor});
update(1, 1, dif, rev[cor], dif, {-1, cor});
}
else
if (bef == - inf) // aft != inf
{
update(1, 1, dif, 1, rev[aft], {1, aft});
update(1, 1, dif, 1, rev[cor], {-1, cor});
int mid = (cor + aft) / 2;
update(1, 1, dif, rev[cor], rev[mid], {-1, cor});
update(1, 1, dif, rev[mid] + 1, rev[aft], {-1, aft});
}
else
if (aft == inf) // bef != inf
{
update(1, 1, dif, rev[bef], dif, {1, bef});
update(1, 1, dif, rev[cor], dif, {-1, cor});
int mid = (bef + cor) / 2;
update(1, 1, dif, rev[bef], rev[mid], {-1, bef});
update(1, 1, dif, rev[mid] + 1, rev[cor], {-1, cor});
}
else /// aft != inf && bef != inf
{
int mid = (bef + aft) / 2;
update(1, 1, dif, rev[bef], rev[mid], {1, bef});
update(1, 1, dif, rev[mid] + 1, rev[aft], {1, aft});
int mid_left = (bef + cor) / 2;
update(1, 1, dif, rev[bef], rev[mid_left], {-1, bef});
update(1, 1, dif, rev[mid_left] + 1, rev[cor], {-1, cor});
int mid_right = (cor + aft) / 2;
update(1, 1, dif, rev[cor], rev[mid_right], {-1, cor});
update(1, 1, dif, rev[mid_right] + 1, rev[aft], {-1, aft});
}
act[type].erase(it);
}
int ans[maxn];
int single_query(int cor)
{
/**int far = 0;
for (int i = 1; i <= k; i ++)
{
multiset < int > :: iterator it = act[i].upper_bound(cor);
int closest = inf;
///if (it != act[i].end())
///cout << "here " << cor << " " << *it << endl;
if (it != act[i].end())
closest = min(closest, *it - cor);
if (it != act[i].begin())
closest = min(closest, cor - *prev(it));
far = max(far, closest);
///cout << far << endl;
}*/
int far = query(1, 1, dif, rev[cor], cor);
if (far > 2e8)
return -1;
return far;
}
void answer_queries()
{
sort(task + 1, task + q + 1, cmp_query);
vector < event > events;
for (int i = 1; i <= n; i ++)
{
events.push_back(event(s[i].t, s[i].x, 1, s[i].a));
events.push_back(event(s[i].t, s[i].x, -1, s[i].b + 1));
}
sort(events.begin(), events.end(), cmp_event);
for (int i = 1; i <= k; i ++)
{
act[i].insert(-inf);
act[i].insert(inf);
update(1, 1, dif, 1, dif, {1, -inf});
}
int pt = 1;
for (event cur : events)
{
while(pt <= q && task[pt].y < cur.arrive)
{
ans[task[pt].idx] = single_query(task[pt].l);
pt ++;
}
if (cur.add == 1)
add_event(cur.type, cur.cor);
else
remove_event(cur.type, cur.cor);
}
while(pt <= q)
{
ans[task[pt].idx] = single_query(task[pt].l);
pt ++;
}
for (int i = 1; i <= q; i ++)
cout << ans[i] << endl;
}
void solve()
{
input();
compress_data();
answer_queries();
}
int main()
{
solve();
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
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message
new_home.cpp: In function 'void compress_data()':
new_home.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < cor.size(); i ++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
76120 KB |
Output is correct |
| 2 |
Correct |
14 ms |
76124 KB |
Output is correct |
| 3 |
Correct |
15 ms |
76124 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
76124 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
76120 KB |
Output is correct |
| 2 |
Correct |
14 ms |
76124 KB |
Output is correct |
| 3 |
Correct |
15 ms |
76124 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
76124 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
758 ms |
254460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
744 ms |
238388 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
76120 KB |
Output is correct |
| 2 |
Correct |
14 ms |
76124 KB |
Output is correct |
| 3 |
Correct |
15 ms |
76124 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
76124 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
76120 KB |
Output is correct |
| 2 |
Correct |
14 ms |
76124 KB |
Output is correct |
| 3 |
Correct |
15 ms |
76124 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
76124 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
