#include<bits/stdc++.h>
using namespace std;
map<int,vector<pair<int,int>>> ad,del,qr;
int ans[100100];
multiset<int>stor[401];
set<int>stuffhappens;
struct segtree{
int rt,CC;
int lc[1<<20],rc[1<<20], vl[1<<20];
segtree(){rt=CC=0;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(!i) i=++CC;
if(ll<=l&&r<=rr) return void(vl[i]=max(vl[i],v));
update(lc[i],l,l+r>>1,ll,rr,v);
update(rc[i],l+r+2>>1,r,ll,rr,v);
}
int query(int i,int l,int r,int p){
if(!i) return -2e9;
if(l+r>>1<p)
return max(vl[i],query(rc[i],l+r+2>>1,r,p));
return max(vl[i],query(lc[i],l,l+r>>1,p));
}
void upd(int l,int r,int v){
update(rt,1,1e8,l,r,v);
}
int qry(int p) {
return query(rt,1,1e8,p);
}
} seg1,seg2;
void a_range(int l,int r){
seg1.upd(l,l+r>>1,-l);
seg2.upd(l+r+2>>1,r,r);
}
int main(){
cin.tie(0)->sync_with_stdio(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);
del[r+1].push_back({a,b});
stuffhappens.insert(r+1);
}
for(int i=1;i<=k;i++)
stor[i].insert(-1e9),stor[i].insert(1e9);
for(int i=0;i<q;i++){
int x,y; cin>>x>>y;
qr[y].push_back({x,i});
stuffhappens.insert(y);
}
for(int i=1;i<=k;i++){
auto it=++stor[i].begin();
while(it!=stor[i].end()){
a_range(*prev(it),*it);
it++;
}
}
for(auto year:stuffhappens){
for(auto[p,t]:del[year]) {
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));
}
for(auto[p,i]:qr[year])
ans[i]=max(seg1.qry(p)+p,seg2.qry(p)-p);
}
for(int i=0;i<q;i++)
cout<<(ans[i]>1e8?-1:ans[i])<<'\n';
}
Compilation message
new_home.cpp: In member function 'void segtree::update(int&, int, int, int, int, int)':
new_home.cpp:15:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
15 | update(lc[i],l,l+r>>1,ll,rr,v);
| ~^~
new_home.cpp:16:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
16 | update(rc[i],l+r+2>>1,r,ll,rr,v);
| ~~~^~
new_home.cpp: In member function 'int segtree::query(int, int, int, int)':
new_home.cpp:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | if(l+r>>1<p)
| ~^~
new_home.cpp:21:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | return max(vl[i],query(rc[i],l+r+2>>1,r,p));
| ~~~^~
new_home.cpp:22:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | return max(vl[i],query(lc[i],l,l+r>>1,p));
| ~^~
new_home.cpp: In function 'void a_range(int, int)':
new_home.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | seg1.upd(l,l+r>>1,-l);
| ~^~
new_home.cpp:33:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | seg2.upd(l+r+2>>1,r,r);
| ~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
17240 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
941 ms |
283672 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8540 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
8540 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
