#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 (20006)
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,block[MAXN];
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]));
FOR(i,0,siz(d)-2){
FOR(j,1,siz(rows[i])-1){
if(rows[i+1].back().f<rows[i][j].f) break;
if(lbd(rows[i+1],pi(rows[i][j].f,0)) == lbd(rows[i+1],pi(rows[i][j-1].f,0))){
block[rows[i][j-1].s]=1;
}
}
}
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(block[ind]==1||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,x=qu[i.s].s.f,y=qu[i.s].s.s;
-- x;
ll lol=lbd(d,a);
auto check=[&](ll ppl){
if(num[ppl]==-1)return 0;
ll pos=siz(dq[num[ppl]])-1-order[ppl];
if(pos+x-a<siz(dq[num[ppl]]))return 1;
else return 0;
};
ll st=-1,en=siz(rows[lol]);
while(en-st>1){
ll mid=(st+en)>>1;
if(check(rows[lol][mid].s)) en=mid;
else st=mid;
}
// FOR(i,1,siz(rows[lol])-1)assert(check(rows[lol][i].s)>=check(rows[lol][i-1].s));
// if(en==siz(rows[lol]))continue;
// ll guy1=rows[lol][en].s,pos=siz(dq[num[guy1]])-1-order[guy1];
// if(dq[num[guy1]][pos+x-a]>y)continue;
ll ind=i.s;
FOR(i,0,siz(rows[lol])-1){
ll guy1=rows[lol][i].s;
if(num[guy1]==-1)continue;
ll pos=siz(dq[num[guy1]])-1-order[guy1];
if(pos+x-a<siz(dq[num[guy1]])&&dq[num[guy1]][pos+x-a]<=y) ans[ind]=1;
}
}
}
FOR(i,1,q)cout<<(ans[i]?"Yes":"No")<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
21588 KB |
expected YES, found NO [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
5488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
5484 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
15616 KB |
expected YES, found NO [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
5492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
