#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
const ll inf=1e15;
const ll maxn=2e5+5;
vector<ii> tramps;
ll lo[maxn],hi[maxn];
struct qry{
ll r1,c1,r2,c2,id;
qry(ll a,ll b, ll c, ll d, ll e){
r1=a,c1=b,r2=c,c2=d,id=e;
}
};
vector<qry> queries;
void dnc(ll l, ll r, vector<ii> tramp, vector<qry> que){
ll m=(l+r)>>1;
cerr<<l<<' '<<r<<endl;
if (l==r){
sort(tramp.begin(),tramp.end());
for (auto u:que){
ll lpos=lower_bound(tramp.begin(),tramp.end(),make_pair(u.r1,u.c1))
-tramp.begin();
ll rpos=upper_bound(tramp.begin(),tramp.end(),make_pair(u.r2,u.c2))
-tramp.begin();
if (rpos-lpos==u.r2-u.r1) lo[u.id]=inf;
}
return;
}
vector<ii> lt,rt; // left tramp, right tramp
vector<qry> lq,rq,uq; //left query, right query, useful query
for (auto u:que){
if (u.c1>m) rq.emplace_back(u.r1,u.c1,u.r2,u.c2,u.id);
else if (u.c2<=m) lq.emplace_back(u.r1,u.c1,u.r2,u.c2,u.id);
else uq.emplace_back(u.r1,u.c1,u.r2,u.c2,u.id);
}
for (auto u:tramp){
if (u.second>m) rt.emplace_back(u.first+1,u.second);
else lt.emplace_back(u);
}
vector<ll> lh(lt.size()),rh(rt.size()); // left tramp lowest height, right tramp highest height
sort(lt.begin(),lt.end()); //eval highest trampolines first
sort(rt.begin(),rt.end()); //eval lowest trampolines first
for (int i=lt.size()-1;i>=0;i--){
lh[i]=lt[i].first+1;
ll pos=lower_bound(lt.begin(),lt.end(),make_pair(lt[i].first+1,lt[i].second))
-lt.begin();
if (lt[pos].first==lt[i].first+1) lh[i]=lh[pos];
cerr<<lh[i]<<' '<<lt[i].first<<' '<<lt[i].second<<endl;
}
for (int i=0;i<rt.size();i++){
rh[i]=rt[i].first-1;
ll pos=upper_bound(rt.begin(),rt.end(),make_pair(rt[i].first-1,rt[i].second))
-rt.begin();
if (rt[pos].first==rt[i].first-1) rh[i]=rh[pos];
cerr<<rh[i]<<' '<<rt[i].first<<' '<<rt[i].second<<endl;
}
vector<tuple<ll,ll,ll>> s,e;
for (auto u:uq){
ll pos=lower_bound(lt.begin(),lt.end(),make_pair(u.r1,u.c1))
-lt.begin();
if (pos==lt.size() || u.r1!=lt[pos].first) lo[u.id]=u.r1;
else lo[u.id]=lh[pos];
pos=upper_bound(rt.begin(),rt.end(),make_pair(u.r2,u.c2))
-rt.begin();
pos--;
if (pos==-1 || u.r2!=rt[pos].first) hi[u.id]=u.r2;
else hi[u.id]=rh[pos];
cerr<<u.r2<<' '<<rt[pos].first<<endl;
cerr<<u.id<<' '<<lo[u.id]<<' '<<hi[u.id]<<'x'<<endl;
}
for (auto &u:rt){
u.first-=1;
}
dnc(l,m,lt,lq);
dnc(m+1,r,rt,rq);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll r,c,t;
cin>>r>>c>>t;
ll a,b;
for (int i=1;i<=t;i++){
cin>>a>>b;
tramps.emplace_back(a,b);
}
ll q,e,d;
cin>>q;
for (int i=1;i<=q;i++){
cin>>a>>b>>e>>d;
if (a>e || b>d){
lo[i]=-inf;
continue;
}
queries.emplace_back(a,b,e,d,i);
}
dnc(1,c,tramps,queries);
for (int i=1;i<=q;i++) cout<<(lo[i]>=hi[i]?"Yes":"No")<<endl;
return 0;
}
Compilation message
trampoline.cpp: In function 'void dnc(long long int, long long int, std::vector<std::pair<long long int, long long int> >, std::vector<qry>)':
trampoline.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i=0;i<rt.size();i++){
| ~^~~~~~~~~~
trampoline.cpp:64:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | if (pos==lt.size() || u.r1!=lt[pos].first) lo[u.id]=u.r1;
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
450 ms |
4260 KB |
expected YES, found NO [5th token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2086 ms |
25508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2020 ms |
90676 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2059 ms |
9644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2049 ms |
47808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
