#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
typedef long long ll;
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (400006)
ll r,c,n,q,other[MAXN];
pi A[MAXN],pos[MAXN];
vector<ll> d,dc;
vector<pi> row[MAXN];
bitset<MAXN>ans;
int p[MAXN];
int find(int x) { return (p[x]==x) ? x : p[x]=find(p[x]); }
void merge(int x,int y){return void(p[find(x)]=find(y)); }
bool same(int a,int b){return find(a)==find(b);}
vector<spi> e,col[MAXN],Q;
bitset<MAXN>vis;
int main(){
FAST
cin>>r>>c>>n;
FOR(i,1,n){
cin>>A[i].f>>A[i].s;
d.eb(A[i].f), d.eb(A[i].f+1), dc.eb(A[i].s);
}
sort(all(d)), d.resize(unique(all(d))-d.begin());
sort(all(dc)), dc.resize(unique(all(dc))-dc.begin());
FOR(i,1,n){
row[lbd(d,A[i].f)].eb(A[i].s, i*2-1);
row[lbd(d,A[i].f+1)].eb(A[i].s, i*2);
col[lbd(dc,A[i].s)].eb(A[i].s, pi(i*2-1,i*2));
}
FOR(ii,0,siz(d)-1){
sort(all(row[ii]),[](pi x,pi y){if(x.f^y.f)return x.f<y.f;else return (x.s&1) < (y.s&1);});
FOR(i,0,siz(row[ii])-2){
col[lbd(dc,row[ii][i].f)].eb(row[ii][i+1].f,pi(row[ii][i].s,row[ii][i+1].s));
}
}
cin>>q;
FOR(i,1,q){
ll a,b,x,y;
cin>>a>>b>>x>>y;
auto exist=[&](ll a,ll b){
ll pos1=lbd(d,a);
if(pos1==d.size()||d[pos1]!=a)return 0;
ll pos2=lbd(d,b);
if(pos2==d.size()||d[pos2]!=b)return 0;
return int(pos2-pos1==b-a);
};
if(a>x||((!exist(a,x))&&a!=x)||b>y) ans[i]=0;
else if(a==x) ans[i]=1;
else {
ll p1=lbd(d,a),p2=lbd(d,x);
pos[i].f=lbd(row[p1],pi(b,0));
pos[i].s=ubd(row[p2],pi(y,LLINF))-1;
if(pos[i].f==row[p1].size()||pos[i].s<0){
ans[i]=0;
continue;
}
pos[i].f=row[p1][pos[i].f].s, pos[i].s=row[p2][pos[i].s].s;
Q.eb(-i,pi(a,b));
Q.eb(i,pi(x,y));
other[i]=y;
}
}
sort(all(Q),[](spi x,spi y){return pi(-x.s.s,x.f)<pi(-y.s.s,y.f);});
ll pre=siz(dc);
for(auto i:Q){
i.s.s=lbd(dc,i.s.s);
while(pre>i.s.s){
-- pre;
for(auto j:col[pre]){
e.eb(j.f,pi(j.s.f,j.s.s));
}
}
if(i.f<0){
i.f*=-1;
FOR(i,0,MAXN-1)p[i]=i;
sort(all(e));
for(auto j:e)if(j.f<=other[i.f]){
merge(j.s.f,j.s.s);
}else break;
ans[i.f]=same(pos[i.f].f,pos[i.f].s);
}
}
FOR(i,1,q)cout<<(ans[i]?"YES":"NO")<<'\n';
}
Compilation message
trampoline.cpp: In lambda function:
trampoline.cpp:66:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos1==d.size()||d[pos1]!=a)return 0;
~~~~^~~~~~~~~~
trampoline.cpp:68:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos2==d.size()||d[pos2]!=b)return 0;
~~~~^~~~~~~~~~
trampoline.cpp: In function 'int main()':
trampoline.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(pos[i].f==row[p1].size()||pos[i].s<0){
~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
23680 KB |
expected NO, found YES [2nd token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2097 ms |
68104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2094 ms |
76756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2099 ms |
22544 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2097 ms |
75232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
