#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=5e5;
const int INF=1e8;
vector<int> fst_,sec_,vec[MAX];
vector<pii> fst,sec,increasing,decreasing;
int N,K,Q,X,Y,Z,l,r,pre,res,Begin,End;
bool cmp(pii X,pii Y)
{
return X.second<Y.second;
}
signed main()
{
ios_base::sync_with_stdio(false);
/*cin.tie(0);
cout.tie(0);*/
Begin=0;
End=INF;
cin>>N>>K>>Q;
for(int A=1;A<=N;A++)
{
cin>>X>>Y>>Z>>Z;
vec[Y].pb(X);
}
for(int A=1;A<=K;A++)
{
if(vec[A].empty())
{
while(Q--)
cout<<-1<<"\n";
return 0;
}
sort(vec[A].begin(),vec[A].end());
for(int B=1;B<vec[A].size();B++)
increasing.pb(mp(vec[A][B-1],(vec[A][B-1]+vec[A][B])/2));
for(int B=vec[A].size()-2;B>=0;B--)
decreasing.pb(mp(vec[A][B+1],(vec[A][B+1]+vec[A][B]+1)/2));
Begin=max(Begin,vec[A][0]);
End=min(End,vec[A].back());
}
sort(increasing.begin(),increasing.end());
sort(decreasing.begin(),decreasing.end(),cmp);
for(int A=0;A<increasing.size();A++)
{
l=max(pre+1,increasing[A].first);
r=increasing[A].second;
if(l>r)
continue;
fst.pb(mp(l,r));
fst_.pb(increasing[A].first);
pre=r;
}
pre=INF+99;
for(int A=decreasing.size()-1;A>=0;A--)
{
l=min(pre-1,decreasing[A].first);
r=decreasing[A].second;
if(l<r)
continue;
sec.pb(mp(r,l));
sec_.pb(decreasing[A].first);
pre=r;
}
reverse(sec.begin(),sec.end());
reverse(sec_.begin(),sec_.end());
/*for(auto A:fst)
cout<<A.first<<" fst "<<A.second<<"\n";
for(auto A:sec)
cout<<A.first<<" sec "<<A.second<<"\n";*/
while(Q--)
{
res=0;
cin>>X>>Y;
if(X<Begin)
{
cout<<Begin-X<<"\n";
continue;
}
else if(X>End)
{
cout<<X-End<<"\n";
continue;
}
int low=0,high=fst.size()-1,mid;
while(low<=high)
{
mid=(low+high)/2;
if(fst[mid].first<=X and fst[mid].second>=X)
{
res=max(res,abs(X-fst_[mid]));
break;
}
else if(fst[mid].second<X)
low=mid+1;
else if(fst[mid].first>X)
high=mid-1;
}
low=0,high=sec.size()-1;
while(low<=high)
{
mid=(low+high)/2;
if(sec[mid].first<=X and sec[mid].second>=X)
{
res=max(res,abs(sec_[mid]-X));
break;
}
else if(sec[mid].second<X)
low=mid+1;
else if(sec[mid].first>X)
high=mid-1;
}
cout<<res<<"\n";
}
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int B=1;B<vec[A].size();B++)
~^~~~~~~~~~~~~~
new_home.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int A=0;A<increasing.size();A++)
~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
12260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
12260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
896 ms |
34768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
965 ms |
40200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
12260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
12260 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
