#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int mod = 1e9 + 7, oo = 1e18 + 7;
/*
Algo (Ig)
*/
int n, k, q;
int a[N], b[N], x[N], t[N];
int l[N], y[N];
vector<int> times;
vector<ii> opes[N << 2];
vector<int> asks[N];
multiset<int> mls[N];
stack<int> mini[N << 2], maxi[N << 2];
vector<int> ask_pos;
// get position to add/erase
ii get_pos(int l, int r){
assert(l <= r);
int temp1 = lower_bound(ask_pos.begin(), ask_pos.end(), l) - ask_pos.begin();
int temp2 = upper_bound(ask_pos.begin(), ask_pos.end(), r) - ask_pos.begin();
temp2--;
if(temp2 < temp1){
// cout << "OK\n";
// exit(0);
}
//assert(temp2 >= temp1);
return {temp1, temp2};
}
void build(int id, int l, int r){
mini[id].push(oo);
maxi[id].push(-oo);
if(l == r) return;
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
// update the minimum & maximum
void add(int id, int l, int r, int L, int R, int val, int type){
if(l > R || r < L || l > r) return;
if(l >= L && r <= R){
if(!type) mini[id].push(min(mini[id].top(), val));
else maxi[id].push(max(maxi[id].top(), val));
return;
}
int mid = (l + r) >> 1;
add(id << 1, l, mid, L, R, val, type);
add(id << 1 | 1, mid + 1, r, L, R, val, type);
}
// erase the lasest changes
void er(int id, int l, int r, int L, int R, int type){
if(l > R || r < L || l > r) return;
if(l >= L && r <= R){
if(!type){
assert(mini[id].size());
mini[id].pop();
}
else{
assert(maxi[id].size());
maxi[id].pop();
}
return;
}
int mid = (l + r) >> 1;
er(id << 1, l, mid, L, R, type);
er(id << 1 | 1, mid + 1, r, L, R, type);
}
int answer[N];
ii ans_que = {oo, -oo};
// easy query stuff
void que(int id, int l, int r, int pos){
ans_que.fi = min(ans_que.fi, mini[id].top());
ans_que.se = max(ans_que.se, maxi[id].top());
if(l == r) return;
int mid = (l + r) >> 1;
if(pos <= mid) que(id << 1, l, mid, pos);
else que(id << 1 | 1, mid + 1, r, pos);
}
// for persistent segment tree
void upd(int id, int l, int r, int L, int R, ii v){
if(l > R || r < L) return;
if(l >= L && r <= R){
opes[id].pb(v);
return;
}
int mid = (l + r) >> 1;
upd(id << 1, l, mid, L, R, v);
upd(id << 1 | 1, mid + 1, r, L, R, v);
}
map<ii, int> answ;// b/c i'm lazy
void trav(int id, int l, int r){
//cout << id << " " << l << " " << r << "\n";
for(auto it : opes[id]){
// cout << id << " " << l << " " << r << " " << it.fi << " " << it.se << "\n";
set<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
if(itt == mls[it.se].end()) exit(0);
assert(itt != mls[it.se].end());
itt2++;
bool ck1 = (itt == mls[it.se].begin()), ck2 = (itt2 == mls[it.se].end());
if(ck1 && ck2){// everything turns into -oo and oo
add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, -oo, 0);
add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, oo, 1);
mls[it.se].erase(itt);
continue;
}
else if(ck1){// the left side is missing
int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
pos--;
if(pos) add(1, 1, ask_pos.size() - 1, 1, pos, (*itt2), 1);
}
else if(ck2){// the right side is missing
itt2--;
itt2--;
int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
if(pos < ask_pos.size()) add(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
}
else{
itt2 = itt3 = itt;
itt2++; itt3--;
int md = ((*itt2) + (*itt3)) / 2;
int pos1 = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt3)) - ask_pos.begin();
int pos2 = upper_bound(ask_pos.begin(), ask_pos.end(), md) - ask_pos.begin();
int pos3 = upper_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
pos2--;
pos3--;
if(pos1 <= pos2) add(1, 1, ask_pos.size() - 1, pos1, pos2, (*itt3), 0);
if(pos2 < pos3) add(1, 1, ask_pos.size() - 1, pos2 + 1, pos3, (*itt2), 1);
}
mls[it.se].erase(itt);
}
if(l == r){
for(auto it : asks[l]){
ans_que = {oo, -oo};
int temp = lower_bound(ask_pos.begin(), ask_pos.end(), it) - ask_pos.begin();
que(1, 1, ask_pos.size() - 1, temp);
answ[{times[l], it}] = max(it - ans_que.fi, ans_que.se - it);
}
}
else{
int mid = (l + r) >> 1;
trav(id << 1, l, mid);
trav(id << 1 | 1, mid + 1, r);
}
reverse(opes[id].begin(), opes[id].end());
for(auto it : opes[id]){
mls[it.se].insert(it.fi);
set<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
assert(itt != mls[it.se].end());
itt2++;
bool ck1 = (itt == mls[it.se].begin()), ck2 = (itt2 == mls[it.se].end());
if(ck1 && ck2){
er(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, 0);
er(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, 1);
continue;
}
else if(ck1){
int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
pos--;
if(pos) er(1, 1, ask_pos.size() - 1, 1, pos, 1);
}
else if(ck2){
itt2--;
itt2--;
int pos = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
if(pos < ask_pos.size()) er(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, 0);
}
else{
itt2 = itt3 = itt;
itt2++; itt3--;
int md = ((*itt2) + (*itt3)) / 2;
int pos1 = lower_bound(ask_pos.begin(), ask_pos.end(), (*itt3)) - ask_pos.begin();
int pos2 = upper_bound(ask_pos.begin(), ask_pos.end(), md) - ask_pos.begin();
int pos3 = upper_bound(ask_pos.begin(), ask_pos.end(), (*itt2)) - ask_pos.begin();
pos2--;
pos3--;
if(pos1 <= pos2) er(1, 1, ask_pos.size() - 1, pos1, pos2, 0);
if(pos2 < pos3) er(1, 1, ask_pos.size() - 1, pos2 + 1, pos3, 1);
}
//mls[it.se].insert(it.fi);
}
}
void process(){
cin >> n >> k >> q;
for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];
for(int i = 1; i <= q; i++){
cin >> l[i] >> y[i];
ask_pos.pb(l[i]);
}
times.pb(0);
times.pb(1);
times.pb(1e8);
for(int i = 1; i <= n; i++){
if(a[i] > 2) times.pb(a[i] - 1);
if((b[i] + 1) < 1e8) times.pb(b[i] + 1);
}
ask_pos.pb(0);
sort(ask_pos.begin(), ask_pos.end());
ask_pos.resize(unique(ask_pos.begin(), ask_pos.end()) - ask_pos.begin());
// push the erase operations
for(int i = 1; i <= q; i++) times.pb(y[i]);
sort(times.begin(), times.end());
times.resize(unique(times.begin(), times.end()) - times.begin());
for(int i = 1; i <= n; i++){
if(a[i] > 1){
int le = 1, ri = lower_bound(times.begin(), times.end(), a[i] - 1) - times.begin();
upd(1, 1, times.size() - 1, le, ri, {x[i], t[i]});
}
if((b[i] + 1 < 1e8)){
int le = lower_bound(times.begin(), times.end(), b[i] + 1) - times.begin(), ri = times.size() - 1;
upd(1, 1, times.size() - 1, le, ri, {x[i], t[i]});
}
}
//exit(0);
// insert the queries
for(int i = 1; i <= q; i++){
int temp = lower_bound(times.begin(), times.end(), y[i]) - times.begin();
asks[temp].pb(l[i]);
}
// initialize (not erase anything)
for(int i = 1; i <= n; i++) mls[t[i]].insert(x[i]);
// cout << ask_pos.size() - 1 << "\n";
// exit(0);
build(1, 1, ask_pos.size() - 1);
for(int i = 1; i <= k; i++){
if(!mls[i].size()){
add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, -oo, 0);
add(1, 1, ask_pos.size() - 1, 1, ask_pos.size() - 1, oo, 1);
continue;
}
//continue;
int lst = -oo;
int cnt = 0;
for(multiset<int>::iterator it = mls[i].begin(); it != mls[i].end(); it++){
int le = 1, ri = 1e8;
if(it != mls[i].begin()){
multiset<int>::iterator it2 = it;
it2--;
le = ((*it) + (*it2)) / 2 + 1;
}
multiset<int>::iterator it2 = it;
it2++;
if(it2 != mls[i].end()) ri = ((*it) + (*it2)) / 2;
// if(le > ri || le == ask_pos.size()) continue;
if(le > ri) continue;
if(le > ask_pos.back()) continue;
ii temp = get_pos(le, ri);
if(temp.fi > temp.se) continue;
temp.se = min(temp.se, (int)ask_pos.size() - 1);
if(temp.fi > temp.se) continue;
int posi = lower_bound(ask_pos.begin(), ask_pos.end(), (*it)) - ask_pos.begin();
if(temp.fi < posi) add(1, 1, ask_pos.size() - 1, temp.fi, posi - 1, (*it), 1);
if(posi <= temp.se) add(1, 1, ask_pos.size() - 1, posi, temp.se, (*it), 0);
}
}
//exit(0);
trav(1, 1, times.size() - 1);
for(int i = 1; i <= q; i++) cout << (answ[{y[i], l[i]}] <= 1e8 ? answ[{y[i], l[i]}] : -1) << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("KEK.inp", "r", stdin);
//freopen("KEK.out", "w", stdout);
cin.tie(0);
process();
}
Compilation message
new_home.cpp: In function 'void trav(long long int, long long int, long long int)':
new_home.cpp:146:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if(pos < ask_pos.size()) add(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
| ~~~~^~~~~~~~~~~~~~~~
new_home.cpp:196:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | if(pos < ask_pos.size()) er(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, 0);
| ~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'void process()':
new_home.cpp:263:13: warning: unused variable 'lst' [-Wunused-variable]
263 | int lst = -oo;
| ^~~
new_home.cpp:264:13: warning: unused variable 'cnt' [-Wunused-variable]
264 | int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
453 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
453 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
417 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
431 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
453 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
453 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
