#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 6e5 + 10, inf = 1e9;
struct store
{
int x, t, a, b;
}s[maxn];
struct query
{
int l, y, idx;
}task[maxn];
int n, k, q;
int readInt () {
bool minus = false;
int result = 0;
char ch;
ch = getchar();
while (true) {
if (ch == '-') break;
if (ch >= '0' && ch <= '9') break;
ch = getchar();
}
if (ch == '-') minus = true; else result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
if (minus)
return -result;
else
return result;
}
void input()
{
n = readInt();
k = readInt();
q = readInt();
///cin >> n >> k >> q;
for (int i = 1; i <= n; i ++)
{
s[i].x = readInt();
s[i].t = readInt();
s[i].a = readInt();
s[i].b = readInt();
/// cin >> s[i].x >> s[i].t >> s[i].a >> s[i].b;
}
for (int i = 1; i <= q; i ++)
{
task[i].l = readInt();
task[i].y = readInt();
task[i].idx = i;
///cin >> task[i].l >> task[i].y, task[i].idx = i;
}
}
unordered_map < int, int > rev;
int dif, back_to[2 * maxn];
bool cmp_query(query &t1, query &t2)
{
return t1.l < t2.l;
}
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 > act[maxn];
struct interval_ray
{
int s, e;
pair < int, int > ray;
interval_ray(int _s, int _e, pair < int, int > _ray)
{
s = _s;
e = _e;
ray = _ray;
}
interval_ray(int &_s, int &_e, pair < int, int > &_ray)
{
s = _s;
e = _e;
ray = _ray;
}
};
vector < interval_ray > seg_left, seg_right;
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
if (hash1 != hash2) {
return hash1 ^ hash2 + std::chrono::high_resolution_clock::now().time_since_epoch().count();
}
// If hash1 == hash2, their XOR is zero.
return hash1 + std::chrono::high_resolution_clock::now().time_since_epoch().count();
}
};
unordered_map < pair < int, int >, int, hash_pair > ray_right[maxn], ray_left[maxn];
vector < int > dat;
void make_left_segment(int start, int finish, int timer, int type)
{
///cout << "left " << start << " " << finish << " " << timer << endl;
seg_left.push_back(interval_ray(ray_left[type][{start, finish}], timer - 1, {start, finish}));
ray_left[type][{start, finish}] = 0;
}
void make_right_segment(int start, int finish, int timer, int type)
{
seg_right.push_back(interval_ray(ray_right[type][{start, finish}], timer - 1, {start, finish}));
ray_right[type][{start, finish}] = 0;
}
void add_event(int type, int cor, int timer)
{
multiset < int > :: iterator it = act[type].upper_bound(cor);
int aft = *it;
int bef = *prev(it);
if (bef == -inf && aft == inf)
{
make_right_segment(-inf, inf, timer, type);
ray_left[type][{cor, -inf}] = timer;
ray_right[type][{cor, +inf}] = timer;
}
else
if (bef == - inf)
{
make_left_segment(aft, -inf, timer, type);
int mid = (cor + aft) / 2;
ray_right[type][{cor, mid}] = timer;
ray_left[type][{aft, mid + 1}] = timer;
ray_left[type][{cor, -inf}] = timer;
}
else
if (aft == inf)
{
make_right_segment(bef, inf, timer, type);
int mid = (bef + cor) / 2;
ray_left[type][{cor, mid + 1}] = timer;
ray_right[type][{bef, mid}] = timer;
ray_right[type][{cor, inf}] = timer;
}
else
{
int mid = (bef + aft) / 2;
make_right_segment(bef, mid, timer, type);
make_left_segment(aft, mid + 1, timer, type);
int mid_left = (bef + cor) / 2;
ray_right[type][{bef, mid_left}] = timer;
ray_left[type][{cor, mid_left + 1}] = timer;
int mid_right = (cor + aft) / 2;
ray_right[type][{cor, mid_right}] = timer;
ray_left[type][{aft, mid_right + 1}] = timer;
}
act[type].insert(cor);
}
void remove_event(int type, int cor, int timer)
{
multiset < int > :: iterator it = act[type].find(cor);
int aft = *next(it);
int bef = *prev(it);
if (bef == -inf && aft == inf)
{
///cout << "reverse " << timer << endl;
make_left_segment(cor, -inf, timer, type);
make_right_segment(cor, +inf, timer, type);
ray_right[type][{-inf, inf}] = timer;
}
else
if (bef == -inf)
{
///cout << "step " << timer << endl;
make_left_segment(cor, -inf, timer, type);
int mid = (cor + aft) / 2;
make_right_segment(cor, mid, timer, type);
make_left_segment(aft, mid + 1, timer, type);
ray_left[type][{aft, -inf}] = timer;
}
else
if (aft == inf)
{
make_right_segment(cor, inf, timer, type);
int mid = (bef + cor) / 2;
make_left_segment(cor, mid + 1, timer, type);
make_right_segment(bef, mid, timer, type);
ray_right[type][{bef, inf}] = timer;
}
else
{
int mid = (bef + aft) / 2;
///assert((ray_right[type][{bef, mid}]) == 0);
///assert((ray_left[type][{aft, mid + 1}]) == 0);
int mid_left = (bef + cor) / 2;
make_right_segment(bef, mid_left, timer, type);
make_left_segment(cor, mid_left + 1, timer, type);
int mid_right = (aft + cor) / 2;
make_right_segment(cor, mid_right, timer, type);
make_left_segment(aft, mid_right + 1, timer, type);
ray_right[type][{bef, mid}] = timer;
ray_left[type][{aft, mid + 1}] = timer;
}
act[type].erase(it);
}
int ans[maxn];
vector < interval_ray > tree_left[maxn * 4], tree_right[maxn * 4];
int pt_lf[4 * maxn], bs_lf[4 * maxn];
int pt_rf[4 * maxn], bs_rf[4 * maxn];
bool cmp_ray_second(interval_ray r1, interval_ray r2)
{
return r1.ray.second < r2.ray.second;
}
void update_range(int root, int left, int right, int qleft, int qright, interval_ray &ray, int type)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
if (type == -1)
tree_left[root].push_back(ray);
else
tree_right[root].push_back(ray);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, ray, type);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, ray, type);
}
unordered_map < int, int > event_times;
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);
ray_right[i][{-inf, inf}] = 1;
}
int cnt = 0;
dat.push_back(1);
dat.push_back(0);
for (event cur : events)
{
///dat.push_back(cur.arrive - 1);
dat.push_back(cur.arrive);
///cout << "event " << cur.arrive << " " << cur.add << " " << cur.cor << " " << cur.type << endl;
if (cur.add == 1)
add_event(cur.type, cur.cor, cur.arrive);
else
remove_event(cur.type, cur.cor, cur.arrive);
}
dat.push_back(inf - 1);
dat.push_back(inf);
for (int i = 1; i <= q; i ++)
dat.push_back(task[i].y);
sort(dat.begin(), dat.end());
cnt ++;
event_times[dat[0]] = cnt;
for (int i = 1; i < dat.size(); i ++)
{
if (dat[i] == dat[i - 1])
continue;
cnt ++;
event_times[dat[i]] = cnt;
}
for (int i = 1; i <= k; i ++)
for (auto it : ray_right[i])
{
///cout << it -> first.first << " :: " << it -> first.second << " " << it -> second << endl;
if (it.second != 0)
make_right_segment(it.first.first, it.first.second, inf, i);
}
for (int i = 1; i <= k; i ++)
for (auto it : ray_left[i])
{
if (it.second != 0)
{
///cout << "here " << endl;
make_left_segment(it.first.first, it.first.second, inf, i);
}
}
sort(seg_right.begin(), seg_right.end(), cmp_ray_second);
sort(seg_left.begin(), seg_left.end(), cmp_ray_second);
for (interval_ray cur : seg_left)
{
//assert(event_times[cur.e + 1] != 0);
update_range(1, 1, cnt, event_times[cur.s], event_times[cur.e + 1] - 1, cur, -1);
/// cout << "left ray " << cur.s << " " << cur.e << " " << cur.ray.first << " " << cur.ray.second << endl;
}
for (interval_ray cur : seg_right)
{
//assert(event_times[cur.e + 1] != 0);
update_range(1, 1, cnt, event_times[cur.s], event_times[cur.e + 1] - 1, cur, 1);
///cout << "right ray " << cur.s << " " << cur.e << " " << cur.ray.first << " " << cur.ray.second << endl;
}
for (int i = 1; i <= 4 * cnt; i ++)
{
pt_rf[i] = (int)(tree_right[i].size()) - 1;
bs_rf[i] = inf;
pt_lf[i] = 0;
bs_lf[i] = -inf;
///sort(tree_right[i].begin(), tree_right[i].end(), cmp_ray_second);
///sort(tree_left[i].begin(), tree_left[i].end(), cmp_ray_second);
}
for (int i = q; i > 0; i --)
{
int longest = 0;
int pos = event_times[task[i].y];
int root = 1, left = 1, right = cnt;
while(true)
{
while(pt_rf[root] >= 0 && task[i].l <= tree_right[root][pt_rf[root]].ray.second)
{
bs_rf[root] = min(bs_rf[root], tree_right[root][pt_rf[root]].ray.first);
pt_rf[root] --;
}
longest = max(longest, task[i].l - bs_rf[root]);
if (left == right)
break;
int mid = (left + right) / 2;
if (pos <= mid)
{
root *= 2;
right = mid;
}
else
{
root = root * 2 + 1;
left = mid + 1;
}
}
ans[task[i].idx] = max(ans[task[i].idx], longest);
}
for (int i = 1; i <= q; i ++)
{
int longest = 0;
int pos = event_times[task[i].y];
int root = 1, left = 1, right = cnt;
while(true)
{
///cout << "step " << root << " " << left << " " << right << endl;
while(pt_lf[root] < tree_left[root].size() && tree_left[root][pt_lf[root]].ray.second <= task[i].l)
{
bs_lf[root] = max(bs_lf[root], tree_left[root][pt_lf[root]].ray.first);
pt_lf[root] ++;
}
longest = max(longest, bs_lf[root] - task[i].l);
/**for (interval_ray cur : tree_left[root])
{
if (task[i].l >= cur.ray.second)
longest = max(longest, cur.ray.first - task[i].l);
}*/
if (left == right)
break;
int mid = (left + right) / 2;
if (pos <= mid)
{
root *= 2;
right = mid;
}
else
{
root = root * 2 + 1;
left = mid + 1;
}
}
ans[task[i].idx] = max(ans[task[i].idx], longest);
}
for (int i = 1; i <= q; i ++)
{
if (ans[i] > 2e8)
cout << -1 << endl;
else
cout << ans[i] << endl;
}
}
void solve()
{
input();
///compress_data();
answer_queries();
}
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int main()
{
speed();
solve();
return 0;
}
/**
2 1 2
3 1 1 3
5 1 3 4
3 3
3 4
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 answer_queries()':
new_home.cpp:340:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
340 | for (int i = 1; i < dat.size(); i ++)
| ~~^~~~~~~~~~~~
new_home.cpp:440:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval_ray>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
440 | while(pt_lf[root] < tree_left[root].size() && tree_left[root][pt_lf[root]].ray.second <= task[i].l)
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In instantiation of 'size_t hash_pair::operator()(const std::pair<_T1, _T2>&) const [with T1 = int; T2 = int; size_t = long unsigned int]':
/usr/include/c++/10/bits/hashtable_policy.h:1379:16: required from 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = std::pair<int, int>; _Value = std::pair<const std::pair<int, int>, int>; _ExtractKey = std::__detail::_Select1st; _H1 = hash_pair; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = long unsigned int]'
/usr/include/c++/10/bits/hashtable_policy.h:734:45: required from 'std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::mapped_type& std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::operator[](std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::key_type&&) [with _Key = std::pair<int, int>; _Pair = std::pair<const std::pair<int, int>, int>; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; _Equal = std::equal_to<std::pair<int, int> >; _H1 = hash_pair; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, false, true>; std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::mapped_type = int; std::__detail::_Map_base<_Key, _Pair, _Alloc, std::__detail::_Select1st, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::key_type = std::pair<int, int>]'
/usr/include/c++/10/bits/unordered_map.h:988:20: required from 'std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type& std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::operator[](std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Hash = hash_pair; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::mapped_type = int; std::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>::key_type = std::pair<int, int>]'
new_home.cpp:146:67: required from here
new_home.cpp:133:34: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
133 | return hash1 ^ hash2 + std::chrono::high_resolution_clock::now().time_since_epoch().count();
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
222044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
222044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2579 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4638 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
222044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
222044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
