#include <bits/stdc++.h>
using namespace std;
//ifstream fin ("trampoline.in");
//ofstream fout ("trampoline.out");
const int MAXN=200010;
const int LGMAX=21;
int n,m,q;
int urm[LGMAX][MAXN];
vector <int> rez;
struct tramp{
int l,c,pos,nr;
}v[MAXN];
bool comp (tramp a, tramp b){
if (a.l==b.l)
return a.c<b.c;
return a.l<b.l;
}
int main()
{
cin >>n>>m>>q;
for (int i=1;i<=q;++i){
cin >>v[i].l>>v[i].c;
v[i].pos=i;
}
sort (v+1,v+q+1,comp);
for (int i=1;i<=n;++i){
}
v[q].nr=1;
for (int i=q-1;i>=1;--i){
if (v[i].l==v[i+1].l)
v[i].nr=v[i+1].nr+1;
else
v[i].nr=1;
}
//gasim fiul fiecarei trambulini verzi, adica prima la dreapta de pe linia imediat urmatoare
for (int i=1;i<=q;++i){
if (i+v[i].nr+v[i+v[i].nr].nr-1>q)
continue;
if (v[i+v[i].nr].l!=v[i].l+1)
continue;
int st=i+v[i].nr,dr=i+v[i].nr+v[i+v[i].nr].nr-1,drk=dr;
while (st<=dr){
int mij=(st+dr)/2;
if (v[mij].c>=v[i].c){
dr=mij-1;
}
else{
st=mij+1;
}
}
if (st>drk)
continue;
urm[0][i]=st;
}
//construim fiul din puteri ale lui 2, asemanator cu rmq
for (int i=1;i<LGMAX;++i){
for (int j=1;j<=q;++j){
if (urm[i-1][urm[i-1][j]]!=0)
urm[i][j]=urm[i-1][urm[i-1][j]];
}
}
int t;
cin >>t;
for (int i=1;i<=t;++i){
int x1,x2,y1,y2;
cin >>x1>>y1>>x2>>y2;
if (x2==x1){
cout <<"Yes"<<'\n';
rez.push_back (1);
continue;
}
int st=1,dr=q;
if (x1<v[1].l or x2>v[q].l+1){
continue;
}
while (st<=dr){
int mij=(st+dr)/2;
if (v[mij].l>=x1)
dr=mij-1;
else
st=mij+1;
}
//cout <<st<<'\n';
if (v[st].l!=x1){
cout <<"No"<<'\n';
rez.push_back (0);
continue;
}
int st1=st,dr1=st+v[st].nr-1;
if (y1>v[dr1].c){
cout <<"No"<<'\n';
rez.push_back (0);
continue;
}
while (st1<=dr1){
int mij=(st1+dr1)/2;
if (v[mij].c>=y1)
dr1=mij-1;
else
st1=mij+1;
}
int dif=x2-x1-1;
if (dif==0){
cout <<"Yes"<<'\n';
rez.push_back (1);
continue;
}
else{
int p=1,x=0,ok=0;
//fout <<urm[0][3];
while (dif){
if ((dif&p)>0){
if (urm[x][st1]==0){
ok=1;
break;
}
else
st1=urm[x][st1];
dif-=p;
}
x++;
p*=2;
}
//fout <<v[st1].l;
if (v[st1].c>y2 or v[st1].l!=x2-1){
cout <<"No"<<'\n';
rez.push_back (0);
}
else{
if (ok==0){
rez.push_back (1);
cout <<"Yes"<<'\n';
}
else{
rez.push_back (0);
cout <<"No"<<'\n';
}
}
}
}
/*for (int i=1;i<=t;++i){
int ok;
string check1;
fin >>check1;
if (check1[0]=='Y')
ok=1;
else
ok=0;
if (ok!=rez[i-1]){
fout <<"Nu e corect";
return 0;
}
}*/
//fout <<"Corect";
return 0;
}
/*
5 5 5
1 1
1 3
2 2
4 4
5 5
5
1 1 2 5
2 3 2 5
3 1 4 5
2 1 5 5
4 3 5 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
6 ms |
724 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
4 ms |
596 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
10756 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
127 ms |
10728 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
120 ms |
11272 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
128 ms |
13412 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
742 ms |
19036 KB |
expected NO, found YES [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
844 KB |
expected NO, found YES [16th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
864 ms |
28772 KB |
expected NO, found YES [54671st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
