#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7,Inf=1e15;
int t,tree[40*N],le_[40*N],ri_[40*N],cur,root[N],n,R,C;
pair<int,int>p[N],a[N];
map<int,int> ind;
set<pair<int,int> > s[N];
void build(int u,int l,int r){
tree[u]=Inf;
if(l==r) {
return;
}
cur++;
le_[u] = cur;
cur++;
ri_[u] = cur;
int mid=(l+r)/2;
build(le_[u],l,mid);
build(ri_[u],mid+1,r);
}
void update(int u,int ind,int l,int r,int val){
if(l>ind || r<ind) return;
if(l==r){
tree[cur]=val;
return;
}
int mid=(l+r)/2,x=cur;
le_[x]=le_[u];
ri_[x]=ri_[u];
cur++;
if(ind<=mid) {
le_[x]=cur;
}
else ri_[x]=cur;
update(le_[u],ind,l,mid,val);
update(ri_[u],ind,mid+1,r,val);
tree[x] = min(tree[le_[x]],tree[ri_[x]]);
}
int getans(int u,int ind,int l,int r){
if(l>ind || r<ind) return Inf;
if(l==r) {
return tree[u];
}
int mid=(l+r)/2;
return min(getans(le_[u],ind,l,mid),getans(ri_[u],ind,mid+1,r));
}
main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// t=1;
cin>>R>>C>>n;
swap(R,C);
for(int i=1;i<=n;i++){
cin>>p[i].f>>p[i].s;
}
sort(p+1,p+n+1);
for(int i=1;i<=n;i++){
a[i].f = p[i].f;
}
int idx = 0;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i].f!=a[i-1].f) idx++;
ind[a[i].f] = idx;
}
root[n+1]=1;
cur=1;
build(1,1,n);
for(int i=n;i>=1;i--){int bef=1;
if(s[ind[p[i].f+1]].upper_bound({p[i].s,0}) != s[ind[p[i].f+1]].end()) {
bef = root [(*s[ind[p[i].f+1]].upper_bound({p[i].s,0})).s ];
}
cur++;root[i] =cur;
update(bef,ind[p[i].f],1,n,p[i].s);
s[ind[p[i].f]].insert({p[i].s,i});
}
cin>>t;
while(t--){
int x,y,x2,y2;
cin>>x>>y>>x2>>y2;
swap(x,y);
swap(x2,y2);
if(y==y2) cout<<"Yes"<<" ";
else
if(s[ind[y]].upper_bound({x,0})==s[ind[y]].end()){
cout<<"No"<<" ";
}
else {
int aft =( *s[ind[y]].upper_bound({x,0})).s;
if(getans(root[aft],ind[y2-1],1,n) <= x2) cout<<"Yes"<< " ";
else cout<<"No"<< " ";
}
}
}
Compilation message
trampoline.cpp:50:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
50 | main(){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
13900 KB |
200 token(s): yes count is 21, no count is 179 |
| 2 |
Correct |
18 ms |
14672 KB |
200 token(s): yes count is 70, no count is 130 |
| 3 |
Correct |
15 ms |
13056 KB |
197 token(s): yes count is 25, no count is 172 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
127452 KB |
4000 token(s): yes count is 99, no count is 3901 |
| 2 |
Correct |
257 ms |
129232 KB |
4000 token(s): yes count is 91, no count is 3909 |
| 3 |
Correct |
250 ms |
128892 KB |
4000 token(s): yes count is 4000, no count is 0 |
| 4 |
Correct |
255 ms |
129168 KB |
4000 token(s): yes count is 1991, no count is 2009 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
611 ms |
129540 KB |
200000 token(s): yes count is 110486, no count is 89514 |
| 2 |
Correct |
641 ms |
140944 KB |
200000 token(s): yes count is 114664, no count is 85336 |
| 3 |
Correct |
636 ms |
139860 KB |
200000 token(s): yes count is 86232, no count is 113768 |
| 4 |
Correct |
691 ms |
139732 KB |
200000 token(s): yes count is 94603, no count is 105397 |
| 5 |
Correct |
680 ms |
139692 KB |
200000 token(s): yes count is 94148, no count is 105852 |
| 6 |
Correct |
798 ms |
143672 KB |
200000 token(s): yes count is 97163, no count is 102837 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
11996 KB |
expected NO, found YES [16th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
903 ms |
133236 KB |
200000 token(s): yes count is 171404, no count is 28596 |
| 2 |
Incorrect |
771 ms |
140936 KB |
expected NO, found YES [22020th token] |
| 3 |
Halted |
0 ms |
0 KB |
- |
