#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int ans[60100];
multiset<int>stor[60100];
set<int>importantyears;
struct segtree{
stack<pair<int,int>>stk;
int rt,CC;
int lc[1<<21],rc[1<<21],vl[1<<21];
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>r) return;
if(ll>rr)return;
if(l>rr||ll>r)return;
if(!i) i=++CC;
if(ll<=l&&r<=rr) return stk.push({i,vl[i]}),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);
}
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<<18],qrys[60010];
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>rr) return;
if(l>r) return;
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){
depth++;
if(depth>1000) exit(0);
if(ll>rr)return;
int CC1=seg1.CC,CC2=seg2.CC;
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);
seg1.CC=CC1,seg2.CC=CC2;
depth--;
}
vector<array<int,4>> stores;
int main(){
cerr<<sizeof seg1;
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);
stores.push_back({a,b,l,r});
}
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;
importantyears.insert(y);
qr[y].push_back({x,i});
compr[y];
}
int CDCC=0;
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[0]=0;
compr[1e9]=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]>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:18:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | update(lc[i],l,l+r>>1,ll,rr,v);
| ~^~
new_home.cpp:19:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | 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:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | if(l+r>>1<p)
| ~^~
new_home.cpp:24:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | return max(vl[i],query(rc[i],l+r+2>>1,r,p));
| ~~~^~
new_home.cpp:25:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
25 | return max(vl[i],query(lc[i],l,l+r>>1,p));
| ~^~
new_home.cpp: In member function 'void segtree::reroll(int)':
new_home.cpp:34: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]
34 | while(stk.size()>k){
| ~~~~~~~~~~^~
new_home.cpp: In function 'void a_range(int, int)':
new_home.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | seg1.upd(l,l+r>>1,-l);
| ~^~
new_home.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | 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:54:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | splatonto(i*2,l,l+r>>1,ll,rr,vl);
| ~^~
new_home.cpp:55:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | 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:73:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | solve(i*2,ll,ll+rr>>1);
| ~~^~~
new_home.cpp:74:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | solve(i*2+1,ll+rr+2>>1,rr);
| ~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 3 |
Correct |
12 ms |
27224 KB |
Output is correct |
| 4 |
Runtime error |
593 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 3 |
Correct |
12 ms |
27224 KB |
Output is correct |
| 4 |
Runtime error |
593 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
823 ms |
374444 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
552 ms |
236716 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 3 |
Correct |
12 ms |
27224 KB |
Output is correct |
| 4 |
Runtime error |
593 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
11 ms |
27228 KB |
Output is correct |
| 3 |
Correct |
12 ms |
27224 KB |
Output is correct |
| 4 |
Runtime error |
593 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
