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;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef array<int,3>pi2;
vector<int>adj[200005];
bool visited[200005];
int two[22][200005];
void dfs(int index, int par){
for(int x=0;x<20;x++){
two[x+1][index]=two[x][two[x][index]];
}
for(auto it:adj[index]){
if(it==par) continue;
two[0][it]=index;
dfs(it,index);
}
}
void solve(){
int n,m,k;
cin >> n >> m >> k;
pii arr[k];
map<int,vector<int>>mp;
for(int x=0;x<k;x++){
cin >> arr[x].first >> arr[x].second;
mp[arr[x].first].push_back(arr[x].second);
}
int ptr=0;
map<pii,int>mp2;
unordered_map<int,pii>hash;
for(auto &it:mp){
sort(it.second.begin(),it.second.end());
for(auto it2:it.second){
hash[ptr]={it.first,it2};
mp2[{it.first,it2}]=ptr++;
}
}
for(auto it:mp){
int nxt=it.first+1;
if(mp.find(nxt)!=mp.end()){
for(auto hold:it.second){
int index=lower_bound(mp[nxt].begin(),mp[nxt].end(),hold)-mp[nxt].begin();
if(index<(int)mp[nxt].size()){
adj[mp2[{it.first,hold}]].push_back(mp2[{nxt,mp[nxt][index]}]);
adj[mp2[{nxt,mp[nxt][index]}]].push_back(mp2[{it.first,hold}]);
}
}
}
}
//for(auto it:mp2){
//show3(a,it.first.first,b,it.first.second,index,it.second);
//}
auto cur=mp.end();
while(cur!=mp.begin()){
cur--;
int sz=cur->second.size();
for(int y=sz-1;y>=0;y--){
int index=mp2[{cur->first,cur->second[y]}];
if(visited[index]) continue;
dfs(index,-1);
}
}
int q;
cin >> q;
pii st,ed;
for(int x=0;x<q;x++){
cin >> st.first >> st.second >> ed.first >> ed.second;
if(st.first==ed.first&&st.second<=ed.second){
cout << "Yes\n";
continue;
}
//go to nearest green
int index=lower_bound(mp[st.first].begin(),mp[st.first].end(),st.second)-mp[st.first].begin();
if(index>=(int)mp[st.first].size()){
cout << "No\n";
continue;
}
int take=mp2[{st.first,mp[st.first][index]}];
for(int y=19;y>=0;y--){
if(hash[two[y][take]].first<ed.first){
take=two[y][take];
}
}
if(hash[take].first+1==ed.first&&hash[take].second<=ed.second){
cout << "Yes\n";
}
else cout << "No\n";
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
//freopen("in.txt","w",stdout);
while(t--){
solve();
}
}
# | 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... |