#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 (200006)
ll r,c,n,q,num[MAXN],order[MAXN];
pi A[MAXN];
dpi qu[MAXN];
vector<pi>Q,rows[MAXN];
vector<ll> d,dc,cols[MAXN];
bitset<MAXN>ans;
vector<deque<ll>> dq;
int main(){
FAST
cin>>r>>c>>n;
FOR(i,1,n){
cin>>A[i].f>>A[i].s;
d.eb(A[i].f);
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){
cols[lbd(dc,A[i].s)].pb(i);
rows[lbd(d,A[i].f)].eb(A[i].s,i);
}
FOR(i,0,siz(dc)-1) sort(all(cols[i]),[](int x,int y){return A[x].f>A[y].f;});
FOR(i,0,siz(d)-1) sort(all(rows[i]));
cin>>q;
FOR(i,1,q){
ll a,b,x,y;cin>>a>>b>>x>>y;
qu[i]=dpi(pi(a,b),pi(x,y));
auto exist=[&](ll a,ll b){
ll p1=lbd(d,a),p2=lbd(d,b);
if(p1==siz(d)||d[p1]!=a||p2==siz(d)||d[p2]!=b)return 0;
return int(p2-p1==b-a);
};
if(a>x||(a!=x&&!exist(a,x-1))||b>y) ans[i]=0;
else if(a==x) ans[i]=1;
else{
Q.eb(b,-i), Q.eb(y,i);
}
}
mmst(num,-1);
sort(all(Q),greater<pi>());
ll pre=siz(dc);
for(auto i:Q){
i.f=lbd(dc,i.f);
while(pre>i.f){
--pre;
for(auto ind:cols[pre]){
ll r=lbd(d,A[ind].f);
if(r==siz(d)-1||d[r+1]!=A[ind].f+1||rows[r+1].back().f<A[ind].s){//start new
num[ind]=siz(dq);order[ind]=0;
dq.pb(deque<ll>()={A[ind].s});
}else{
ll guy=rows[r+1][lbd(rows[r+1],pi(A[ind].s,0))].s;
num[ind]=num[guy];assert(~num[ind]);order[ind]=dq[num[ind]].size();
dq[num[ind]].push_front(A[ind].s);
FOR(i,1,siz(dq[num[ind]])-1)assert(dq[num[ind]][i]>=dq[num[ind]][i-1]);
}
}
}
if(i.s<0){
i.s*=-1;
ll a=qu[i.s].f.f,b=qu[i.s].f.s,x=qu[i.s].s.f,y=qu[i.s].s.s;
-- x;
ll guy1=lbd(rows[lbd(d,a)],pi(b,0));
if(guy1==rows[lbd(d,a)].size()) continue;
guy1=rows[lbd(d,a)][guy1].s; assert(~num[guy1]);
ll pos=siz(dq[num[guy1]])-1-order[guy1];
if(siz(dq[num[guy1]])-pos<x-a+1)continue;
if(dq[num[guy1]][pos+x-a]>y)continue;
ans[i.s]=1;
}
}
FOR(i,1,q)cout<<(ans[i]?"Yes":"No")<<'\n';
}
Compilation message
trampoline.cpp: In function 'int main()':
trampoline.cpp:92:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(guy1==rows[lbd(d,a)].size()) continue;
~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
12288 KB |
expected NO, found YES [2nd token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
482 ms |
30808 KB |
expected NO, found YES [2nd token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2088 ms |
40540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
12160 KB |
expected NO, found YES [59th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2089 ms |
42668 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
