#include<iostream>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e5+1,Q=3e5+1,K=3e5+1;
int n,k,q;
struct pt{
ll x,tp,t;//<0: add, =0: qry, >0: rmv
};
bool operator<(pt x,pt y){
return x.t<y.t;
}
pt a[2*N];
multiset<ll>s[K];
map<pair<ll,ll>,vector<ll> >mp;//should clear after inserting all stores :)
struct upd{
ll x,l,r,pos;
};
bool operator<(upd x,upd y){
return x.pos<y.pos;
}
vector<upd>pve,nve;
string f(ll x){
string ret;
if(x<=-1e8) return "-inf";
if(x>=1e8) return "inf";
if(x==0) ret+='0';
while(x>0){
char c=x%10+48;
x/=10;
ret=c+ret;
}
return ret;
}
void add(ll xl,ll xr,ll t){
mp[{xl,xr}].push_back(t);
}
void rmv(ll xl,ll xr,ll t){
ll p=mp[{xl,xr}].back();
mp[{xl,xr}].pop_back();
if(mp[{xl,xr}].empty()) mp.erase({xl,xr});
if(p==t) return;t--;
upd pl={-xl,p,t,-(xl+xr)/2};
upd nl={xr,p,t,(xl+xr+1)/2};
pve.push_back(pl);nve.push_back(nl);
}
ll ans[Q];
pair<ll,ll>b[Q],c[Q];
ll st[1<<20];
void init(int id,int l,int r){
st[id]=-1e9;
if(l==r) return;
int mid=(l+r)/2;
init(id*2,l,mid);init(id*2+1,mid+1,r);
}
void upd(int id,int l,int r,int ql,int qr,ll v){
if(l>qr || r<ql) return;
if(ql<=l && r<=qr){
st[id]=max(st[id],v);
return;
}
int mid=(l+r)/2;
upd(id*2,l,mid,ql,qr,v);
upd(id*2+1,mid+1,r,ql,qr,v);
}
ll qry(int id,int l,int r,int p){
if(l==r) return st[id];
int mid=(l+r)/2;
if(p<=mid) return max(st[id],qry(id*2,l,mid,p));
else return max(st[id],qry(id*2+1,mid+1,r,p));
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> k >> q;
for(int i=1; i<=n ;i++){
ll x,tp,u,v;cin >> x >> tp >> u >> v;
a[i*2-1]={x,-tp,u};
a[i*2]={x,tp,v+1};
}
for(int i=1; i<=k ;i++){
s[i].insert(-1e9);
s[i].insert(1e9);
mp[{(ll)-1e9,(ll)1e9}].push_back(1);
}
sort(a+1,a+2*n+1);
for(int i=1; i<=2*n ;i++){
ll x=a[i].x,tp=a[i].tp,t=a[i].t;
if(tp<0){
tp=-tp;
auto it=s[tp].lower_bound(x);
auto it2=it;--it2;
rmv(*it2,*it,t);add(*it2,x,t);add(x,*it,t);
s[tp].insert(x);
}
else{
s[tp].erase(s[tp].lower_bound(x));
auto it=s[tp].lower_bound(x);
auto it2=it;--it2;
rmv(*it2,x,t);rmv(x,*it,t);add(*it2,*it,t);
}
}
for(int i=1; i<=k ;i++) rmv(-1e9,1e9,1e9);
sort(nve.begin(),nve.end());
sort(pve.begin(),pve.end());
for(int i=1; i<=q ;i++){
cin >> b[i].fi >> b[i].se;
c[i]={b[i].se,i};
}
sort(c+1,c+q+1);
for(int i=1; i<=q ;i++) b[c[i].se].se=i;
sort(b+1,b+q+1);
int ptr=0;
init(1,1,q);
for(int i=1; i<=q ;i++){
while(ptr<nve.size() && nve[ptr].pos<=b[i].fi){
int l=lower_bound(c+1,c+q+1,(pair<ll,ll>){nve[ptr].l,0LL})-c;
int r=lower_bound(c+1,c+q+1,(pair<ll,ll>){nve[ptr].r+1,0LL})-c-1;
if(l<=r) upd(1,1,q,l,r,nve[ptr].x);
ptr++;
}
ans[b[i].se]=max(ans[b[i].se],qry(1,1,q,b[i].se)-b[i].fi);
}
init(1,1,q);
reverse(b+1,b+q+1);
for(int i=1; i<=q ;i++) b[i].fi=-b[i].fi;
ptr=0;
for(int i=1; i<=q ;i++){
while(ptr<pve.size() && pve[ptr].pos<=b[i].fi){
int l=lower_bound(c+1,c+q+1,(pair<ll,ll>){pve[ptr].l,0LL})-c;
int r=lower_bound(c+1,c+q+1,(pair<ll,ll>){pve[ptr].r+1,0LL})-c-1;
if(l<=r) upd(1,1,q,l,r,pve[ptr].x);
ptr++;
}
ans[b[i].se]=max(ans[b[i].se],qry(1,1,q,b[i].se)-b[i].fi);
}
for(int i=1; i<=q ;i++){
if(ans[i]>=(ll)1e8) cout << "-1\n";
else cout << ans[i] << '\n';
}
}
Compilation message
new_home.cpp: In function 'void rmv(ll, ll, ll)':
new_home.cpp:47:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(p==t) return;t--;
^~
new_home.cpp:47:18: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(p==t) return;t--;
^
new_home.cpp: In function 'int main()':
new_home.cpp:120:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<nve.size() && nve[ptr].pos<=b[i].fi){
~~~^~~~~~~~~~~
new_home.cpp:133:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<pve.size() && pve[ptr].pos<=b[i].fi){
~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
14584 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14460 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
14584 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14460 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3491 ms |
123604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4152 ms |
150320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
14584 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14460 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
14584 KB |
Output is correct |
| 2 |
Correct |
14 ms |
14460 KB |
Output is correct |
| 3 |
Correct |
13 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
14456 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
