#include<bits/stdc++.h>
#define ll long long
const int inf=1e8;
using namespace std;
int x[310005],t[610005],st[1210005],ans[310005];
vector<array<int,2>>v1[310005];
array<int,4>v2[1210005];
array<int,3>qa[310005];
struct comp
{
bool operator () (const int &a,const int &b) const
{
if (x[a]==x[b])
return a<b;
return x[a]<x[b];
}
};
map<int,int,comp>mp;
int u2=0,n,k,q;
void calc()
{
int i;
for(i=0;i<k;i++){
mp[n+1]=0;
for(auto it:v1[i]){
auto it1=mp.upper_bound(it[1]),it2=it1--;
v2[u2++]={(x[it1->first]+x[it2->first]+1)/2,x[it2->first],it2->second,it[0]};
it2->second=it[0];
if (it1->first==it[1]){
it2=it1--;
v2[u2++]={(x[it1->first]+x[it[1]]+1)/2,x[it[1]],it2->second,it[0]};
mp.erase(it2);
}
else
mp[it[1]]=it[0];
}
v2[u2++]={0,2*inf,mp[n+1],2*n+1};
}
sort(v2,v2+u2);
int j=0;
for(i=0;i<q;i++){
while(j<u2 && v2[j][0]<=qa[i][0]){
int l=v2[j][2]+2*n+1;
int r=v2[j][3]+2*n+1;
while(l<r){
if (l%2==1)
st[l]=max(v2[j][1],st[l]);
if (r%2==1)
st[r-1]=max(v2[j][1],st[r-1]);
++l/=2;
r=r/2;
}
++j;
}
for(e=qa[i][2]+2*n+1;e>=1;e=e/2)
ans[qa[i][1]]=max(ans[qa[i][1]],st[e]-qa[i][0]);
}
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d%d",&n,&k,&q);
int i;
for(i=0;i<n;i++){
int aux;
scanf("%d%d%d%d",&x[i],&aux,&t[2*i],&t[2*i+1]);
--aux;
++t[2*i+1];
v1[aux].push_back({t[2*i],i});
v1[aux].push_back({t[2*i+1],i});
}
x[n]=-2*inf;
x[n+1]=2*inf;
sort(t,t+2*n+1);
for(i=0;i<k;i++){
for(auto &it:v1[i])
it[0]=lower_bound(t,t+2*n+1,it[0])-t;
sort(v1[i].begin(),v1[i].end());
}
for(i=0;i<q;i++){
scanf("%d%d",&qa[i][0],&qa[i][2]);
qa[i][2]=upper_bound(t,t+2*n+1,qa[i][2])-t-1;
qa[i][1]=i;
}
sort(qa,qa+q);
mp[n]=0;
calc();
for(i=0;i<n;i++)
x[i]=inf-x[i];
for(i=0;i<q;i++)
qa[i][0]=inf-qa[i][0];
reverse(qa,qa+q);
u2=0;
memset(st,0,sizeof(st));
calc();
for(i=0;i<q;i++)
if (ans[i]>=inf)
printf("-1\n");
else
printf("%d\n",ans[i]);
return 0;
}
Compilation message
new_home.cpp: In function 'void calc()':
new_home.cpp:55:13: error: 'e' was not declared in this scope
55 | for(e=qa[i][2]+2*n+1;e>=1;e=e/2)
| ^
new_home.cpp: In function 'int main()':
new_home.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
63 | scanf("%d%d%d",&n,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | scanf("%d%d%d%d",&x[i],&aux,&t[2*i],&t[2*i+1]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
82 | scanf("%d%d",&qa[i][0],&qa[i][2]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
