#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const int MN = 200200;
const int LOG = 20;
ll nx[MN][LOG];
struct Q {
ll id;
pl st,ed;
bool operator< (const Q& other) {
return st.second < other.st.second;
}
};
vector<Q> qu;
vector<pl> tr;
map<ll,ll> mu;
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll mr,mc;
cin >> mr >> mc;
ll n,N;
cin >> n;
for(int i=0;i<n;i++) {
ll a,b;
cin >> a >> b;
tr.emplace_back(a,b);
}
sort(tr.begin(),tr.end(),[&](const pl& a, const pl& b){
if(a.second > b.second) {return true;}
return a.first > b.first;
});
cin >> N;
vector<ll> ans(N,0);
for(int i=0;i<N;i++) {
ll sr,sc,tr,tc;
cin >> sr >> sc >> tr >> tc;
qu.push_back({i,{sr,sc},{tr,tc}});
}
ll trp = 0;
sort(qu.begin(),qu.end());
for(int i=N-1;i>=0;i--) {
Q q = qu[i];
while(trp < tr.size() && tr[trp].second >= q.st.second) {
ll r = tr[trp].first;
mu[r] = trp;
if(mu.count(r+1)) {
nx[trp][0] = mu[r+1];
} else {
nx[trp][0] = trp;
}
for(int i=1;i<LOG;i++) {
nx[trp][i] = nx[nx[trp][i-1]][i-1];
}
trp++;
}
ll idx = q.id;
if(q.st.first == q.ed.first) {
if(q.st.second <= q.ed.second) {
ans[idx] = 1;
} else {
ans[idx] = 0;
}
} else if(!mu.count(q.st.first)) {
ans[idx] = 0;
} else {
ll no = mu[q.st.first];
ll dif = q.ed.first-q.st.first-1;
if(dif < 0) {ans[idx] = 0;} else {
for(int i=LOG-1;i>=0;i--) {
if(dif&(1<<i)) {
no = nx[no][i];
}
}
}
if(tr[no].first+1 == q.ed.first && tr[no].second <= q.ed.second) {
ans[idx] = 1;
} else {
ans[idx] = 0;
}
}
}
for(int i=0;i<N;i++) {
cout << (ans[i]?"Yes":"No") << '\n';
}
}
Compilation message
trampoline.cpp: In function 'int main()':
trampoline.cpp:44:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while(trp < tr.size() && tr[trp].second >= q.st.second) {
| ~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
1136 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 |
Execution timed out |
2095 ms |
5988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
5860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1992 KB |
expected YES, found NO [1st token] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2088 ms |
7648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
