#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
int ans[300100];
multiset<int>stor[300100];
map<int,int>importpos;
struct segtree{
stack<pair<int,int>>stk;
int vl[1<<20];
segtree(){for(auto&i:vl)i=-2e9;}
void update(int i,int l,int r,int ll,int rr,int v){
if(l>rr||ll>r)return;
if(ll<=l&&r<=rr) return stk.push({i,vl[i]}),void(vl[i]=max(vl[i],v));
update(i*2,l,l+r>>1,ll,rr,v);
update(i*2+1,l+r+2>>1,r,ll,rr,v);
}
int query(int i,int l,int r,int p){
if(l==r) return vl[i];
if(l+r>>1<p)
return max(vl[i],query(i*2+1,l+r+2>>1,r,p));
return max(vl[i],query(i*2,l,l+r>>1,p));
}
void upd(int l,int r,int v){
update(1,1,importpos.size(),importpos.lower_bound(l)->second,
(--importpos.upper_bound(r))->second,v);
}
int qry(int p) {
return query(1,1,importpos.size(),importpos[p]);
}
void reroll(int k){
while(stk.size()>k){
auto[a,b]=stk.top();
stk.pop();
vl[a]=b;
}
}
} seg1,seg2;
vector<pair<int,int>>todie[1<<20],qrys[300100];
void a_range(int l,int r){
seg1.upd(l,l+r>>1,-l);
seg2.upd(l+r+2>>1,r,r);
}
map<int,vector<pair<int,int>>>qr;
map<int,int>compr;
void splatonto(int i,int l,int r,int ll,int rr,pair<int,int>vl){
if(ll<=l&&r<=rr)
return todie[i].push_back(vl);
if(ll>r||l>rr) return;
splatonto(i*2,l,l+r>>1,ll,rr,vl);
splatonto(i*2+1,l+r+2>>1,r,ll,rr,vl);
}
int depth=0;
void solve(int i,int ll,int rr){
if(ll>rr)return;
int sz1=seg1.stk.size(),sz2=seg2.stk.size();
for(auto[p,t]:todie[i]) {
stor[t].erase(stor[t].find(p));
if(stor[t].find(p)==stor[t].end())
a_range(*--stor[t].lower_bound(p),*stor[t].lower_bound(p));
}
if(ll==rr){
for(auto[p,i]:qrys[ll])
ans[i]=max(seg1.qry(p)+p,seg2.qry(p)-p);
} else {
solve(i*2,ll,ll+rr>>1);
solve(i*2+1,ll+rr+2>>1,rr);
}
for(auto[p,t]:todie[i])
stor[t].insert(p);
seg1.reroll(sz1),seg2.reroll(sz2);
}
vector<array<int,4>> stores;
int main(){
cin.tie(0)->sync_with_stdio(0);
importpos[-2e9]=0;
int n,k,q;
cin>>n>>k>>q;
for(int i=0;i<n;i++){
int l,r,a,b;
cin>>a>>b>>l>>r;
stor[b].insert(a);
stores.push_back({a,b,l,r});
}
for(int i=1;i<=k;i++)
stor[i].insert(-2e9),stor[i].insert(2e9);
for(int i=0;i<q;i++){
int x,y; cin>>x>>y;
qr[y].push_back({x,i});
compr[y];
importpos[x];
}
int CDCC=0,CDC=0;
for(auto&[i,j]:importpos)
j=++CDC;
importpos[2e9]=CDC+1;
for(auto&[i,j]:compr)
j=++CDCC;
for(auto[k,x]:qr){
int ind=compr[k];
for(auto[p,i]:x)
qrys[ind].push_back({p,i});
}
compr[-2e9]=0;
compr[2e9]=CDCC+1;
for(auto[pos,t,l,r]:stores){
int k=(--compr.lower_bound(l))->second;
splatonto(1,1,CDCC,1,k,{pos,t});
k=compr.upper_bound(r)->second;
splatonto(1,1,CDCC,k,CDCC,{pos,t});
}
for(int i=1;i<=k;i++){
auto it=++stor[i].begin();
while(it!=stor[i].end()){
a_range(*prev(it),*it);
it++;
}
}
solve(1,1,CDCC);
for(int i=0;i<q;i++)
cout<<(ans[i]>2e9?-1:ans[i])<<'\n';
}
Compilation message
new_home.cpp: In member function 'void segtree::update(int, int, int, int, int, int)':
new_home.cpp:14:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
14 | update(i*2,l,l+r>>1,ll,rr,v);
| ~^~
new_home.cpp:15:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
15 | update(i*2+1,l+r+2>>1,r,ll,rr,v);
| ~~~^~
new_home.cpp: In member function 'int segtree::query(int, int, int, int)':
new_home.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | if(l+r>>1<p)
| ~^~
new_home.cpp:20:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | return max(vl[i],query(i*2+1,l+r+2>>1,r,p));
| ~~~^~
new_home.cpp:21:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | return max(vl[i],query(i*2,l,l+r>>1,p));
| ~^~
new_home.cpp: In member function 'void segtree::reroll(int)':
new_home.cpp:31:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
31 | while(stk.size()>k){
| ~~~~~~~~~~^~
new_home.cpp: In function 'void a_range(int, int)':
new_home.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | seg1.upd(l,l+r>>1,-l);
| ~^~
new_home.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | seg2.upd(l+r+2>>1,r,r);
| ~~~^~
new_home.cpp: In function 'void splatonto(int, int, int, int, int, std::pair<int, int>)':
new_home.cpp:49:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | splatonto(i*2,l,l+r>>1,ll,rr,vl);
| ~^~
new_home.cpp:50:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | splatonto(i*2+1,l+r+2>>1,r,ll,rr,vl);
| ~~~^~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:65:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | solve(i*2,ll,ll+rr>>1);
| ~~^~~
new_home.cpp:66:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | solve(i*2+1,ll+rr+2>>1,rr);
| ~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
54364 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
54420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
54364 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
54420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1844 ms |
229432 KB |
Output is correct |
| 2 |
Correct |
1456 ms |
156524 KB |
Output is correct |
| 3 |
Correct |
1718 ms |
301560 KB |
Output is correct |
| 4 |
Correct |
1869 ms |
242580 KB |
Output is correct |
| 5 |
Correct |
1347 ms |
147852 KB |
Output is correct |
| 6 |
Correct |
1466 ms |
152964 KB |
Output is correct |
| 7 |
Correct |
1693 ms |
301480 KB |
Output is correct |
| 8 |
Correct |
1676 ms |
243240 KB |
Output is correct |
| 9 |
Correct |
1677 ms |
217664 KB |
Output is correct |
| 10 |
Correct |
1540 ms |
178168 KB |
Output is correct |
| 11 |
Correct |
966 ms |
159264 KB |
Output is correct |
| 12 |
Correct |
1141 ms |
175056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5017 ms |
257548 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
54364 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
54420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
54364 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
54420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
