This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int R,C,N,T,a,b,c,d;
vector<pair<int,int>> ziel;
vector<int> point[200007];
pair<int,int>nast[200007];
int nast2[200007],pom[200007];
map<int,vector<int>>zielone;
map<pair<int,int>,int>mp;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>R>>C>>N;
for(int i=0;i<N;i++){
cin>>a>>b;
mp[{a,b}]=i;
ziel.push_back({a,b});
zielone[a].push_back(b);
}
for(auto i=zielone.begin();i!=zielone.end();i++){
sort((*i).second.begin(),(*i).second.end());
}
//cout<<zielone[2][0]<<" "<<zielone[2][1]<<" ";
for(int i=0;i<N;i++){
//cout<<ziel[i].first<<" "<<ziel[i].second<<" ";
if((int)zielone[ziel[i].first+1].size()==0 || zielone[ziel[i].first+1][(int)zielone[ziel[i].first+1].size()-1]<ziel[i].second){
nast[i]=ziel[i];
nast2[i]=i;
}
else{
nast[i].first=ziel[i].first+1;
nast[i].second=*lower_bound(zielone[ziel[i].first+1].begin(),zielone[ziel[i].first+1].end(),ziel[i].second);
//cout<<" "<<(int)zielone[ziel[i].first].size()<<" ";
nast2[i]=mp[{ziel[i].first+1,*lower_bound(zielone[ziel[i].first+1].begin(),zielone[ziel[i].first+1].end(),ziel[i].second)}];
}
point[i].push_back(nast2[i]);
//cout<<" "<<nast[i].first<<" "<<nast[i].second<<" "<<nast2[i]<<" "<<i<<" ";
}
for(int j=1;j<N+3;j=j<<1){
for(int i=0;i<N;i++){
pom[i]= point[ point[i][point[i].size()-1] ] [point [ point[i][point[i].size()-1] ] .size()-1] ;
}
for(int i=0;i<N+7;i++)
point[i].push_back(pom[i]);
// if(j==4)
// return 0;
}
//cout<<"\n\n\n";
cin>>T;
for(int i=0;i<T;i++){
cin>>a>>b>>c>>d;
if(a>c){
cout<<"No\n";
continue;
}
if(a==c){
if(b<=d)
cout<<"Yes\n";
else
cout<<"No\n";
continue;
}
c--;
if(zielone[a].empty() || zielone[a][zielone[a].size()-1]<b){
if(a==c+1 && b<=d)
cout<<"Yes\n";
else
cout<<"No\n";
continue;
}
int ak=mp[{a,*lower_bound(zielone[a].begin(),zielone[a].end(),b)}];
int logarithm=0;
int ak2=1;
while(ak2*8<=c-a){
ak2*=2;
logarithm++;
}
//cout<<ak<<" ";
while(a!=c){
ak=point[ak][logarithm];
a+=ak2;
while(ak2>c-a){
ak2/=2;
logarithm--;
}
}
if((ziel[ak].first==c) && (ziel[ak].second<=d))
cout<<"Yes\n";
else
cout<<"No\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |