#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,sse4,bmi,abm")
#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 = 1e9 + 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[1048576];
vector<int> asks[N];
multiset<int> mls[N];
int mini[1048576], maxi[1048576];
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] = oo;
maxi[id] = -oo;
if(l == r) return;
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
iii ope[10000005];
int tol = 0, itr = 0;
// 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) return;
if(!type){
if(mini[id] <= val) return;
}
else{
if(maxi[id] >= val) return;
}
if(l >= L && r <= R){
if(!type){
// if(mini[id] <= val) return;
tol++;
itr++;
ope[itr] = {{id, 0}, mini[id]};
mini[id] = val;
}
else{
// if(maxi[id] >= val) return;
tol++;
itr++;
ope[itr] = {{id, 1}, maxi[id]};
maxi[id] = val;
}
//tol++;
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_back();
}
else{
// assert(maxi[id].size());
maxi[id].pop_back();
}
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]);
ans_que.se = max(ans_que.se, maxi[id]);
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";
tol = 0;
for(auto it : opes[id]){
// cout << id << " " << l << " " << r << " " << it.fi << " " << it.se << "\n";
if(mls[it.se].size() == 1){
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].clear();
continue;
}
multiset<int>::iterator itt = mls[it.se].lower_bound(it.fi), itt2 = itt, itt3;
// mls[it.se].erase(itt);
// continue;
// 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){// 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);
}
int temp = tol;
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);
}
assert(itr >= temp);
for(auto it : opes[id]) mls[it.se].insert(it.fi);
for(int i = 1; i <= temp; i++){
if(!ope[itr].fi.se) mini[ope[itr].fi.fi] = ope[itr].se;
else maxi[ope[itr].fi.fi] = ope[itr].se;
itr--;
assert(itr >= 0);
}
/*
reverse(opes[id].begin(), opes[id].end());
for(auto it : opes[id]){
mls[it.se].insert(it.fi);
multiset<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 solve_small(){
for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];
vector<pair<int, ii>> events;
for(int i = 1; i <= q; i++){
cin >> l[i] >> y[i];
ask_pos.pb(l[i]);
}
for(int i = 1; i <= n; i++){
events.pb({a[i], {x[i], t[i]}});
events.pb({b[i] + 1, {-x[i], t[i]}});
}
for(int i = 1; i <= q; i++){
events.pb({y[i], {l[i] + 1e9, 0}});
}
sort(events.begin(), events.end());
for(auto it : events){
if(it.se.se != 0){// update
if(it.se.fi > 0) mls[it.se.se].insert(it.se.fi);
else mls[it.se.se].erase(mls[it.se.se].lower_bound(it.se.fi));
}
else{
int ans = -oo;
int temp = it.se.fi - 1e9;
for(int i = 1; i <= k; i++){
if(!mls[i].size()){
ans = oo;
break;
}
multiset<int>::iterator it2 = mls[i].lower_bound(temp);
int mini = oo;
if(it2 != mls[i].end()) mini = min(mini, (*it2) - temp);
if(it2 != mls[i].begin()){
it2--;
mini = min(mini, temp - (*it2));
}
ans = max(ans, mini);
}
answ[{it.fi, temp}] = ans;
}
}
for(int i = 1; i <= q; i++) cout << (answ[{y[i], l[i]}] <= 1e8 ? answ[{y[i], l[i]}] : -1) << "\n";
exit(0);
}
void process(){
cin >> n >> k >> q;
if(k <= 20){
solve_small();
return;
}
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]) - times.begin();
ri--;
if(le <= ri) 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);
}
}
//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
//exit(0);
trav(1, 1, times.size() - 1);
//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
for(int i = 1; i <= q; i++) cout << (answ[{y[i], l[i]}] <= 1e8 ? answ[{y[i], l[i]}] : -1) << "\n";
//cout << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
cin.tie(0);
process();
}
Compilation message
new_home.cpp: In function 'void trav(int, int, int)':
new_home.cpp:176:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | if(pos < ask_pos.size()) add(1, 1, ask_pos.size() - 1, pos, ask_pos.size() - 1, (*itt2), 0);
| ~~~~^~~~~~~~~~~~~~~~
new_home.cpp: In function 'void process()':
new_home.cpp:353:13: warning: unused variable 'lst' [-Wunused-variable]
353 | int lst = -oo;
| ^~~
new_home.cpp:354:13: warning: unused variable 'cnt' [-Wunused-variable]
354 | int cnt = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
46092 KB |
Output is correct |
| 2 |
Correct |
34 ms |
46116 KB |
Output is correct |
| 3 |
Correct |
26 ms |
46024 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
46036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
46092 KB |
Output is correct |
| 2 |
Correct |
34 ms |
46116 KB |
Output is correct |
| 3 |
Correct |
26 ms |
46024 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
46036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1160 ms |
109900 KB |
Output is correct |
| 2 |
Correct |
1743 ms |
100400 KB |
Output is correct |
| 3 |
Correct |
1061 ms |
109892 KB |
Output is correct |
| 4 |
Correct |
1139 ms |
109864 KB |
Output is correct |
| 5 |
Correct |
916 ms |
99828 KB |
Output is correct |
| 6 |
Correct |
1359 ms |
100168 KB |
Output is correct |
| 7 |
Correct |
954 ms |
109852 KB |
Output is correct |
| 8 |
Correct |
1025 ms |
109976 KB |
Output is correct |
| 9 |
Correct |
1101 ms |
110032 KB |
Output is correct |
| 10 |
Correct |
1103 ms |
110152 KB |
Output is correct |
| 11 |
Correct |
1163 ms |
99988 KB |
Output is correct |
| 12 |
Correct |
767 ms |
109884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4287 ms |
144700 KB |
Output is correct |
| 2 |
Incorrect |
396 ms |
79864 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
46092 KB |
Output is correct |
| 2 |
Correct |
34 ms |
46116 KB |
Output is correct |
| 3 |
Correct |
26 ms |
46024 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
46036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
46092 KB |
Output is correct |
| 2 |
Correct |
34 ms |
46116 KB |
Output is correct |
| 3 |
Correct |
26 ms |
46024 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
46036 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
