# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
306185 | Matteo_Verz | Trampoline (info1cup20_trampoline) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// nu ar fi stricat niste teste :)
/*
`-/oo+/- ``
.oyhhhhhhyo.`od
+hhhhyyoooos. h/
+hhyso++oosy- /s
.yoooossyyo:``-y`
..----.` ``.-/+:.`
`````..-::/.
`..```.-::///`
`-.....--::::/:
`.......--::////:
`...`....---:::://:
`......``..--:::::///:`
`---.......--:::::////+/`
----------::::::/::///++:
----:---:::::///////////:`
.----::::::////////////:-`
`----::::::::::/::::::::-
`.-----:::::::::::::::-
...----:::::::::/:-`
`.---::/+osss+:`
``.:://///-.
*/
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
using namespace std;
const int LOG = 18;
const int N = 2e5;
int dp[5 + LOG][5 + N];
set <pair<int,int>> s[5 + N];
map <int, int> norm;
struct ura{
int x, y, cheie;
bool operator < (const ura a) const{
if(a.x == x) return y < a.y;
return x < a.x;
}
}v[5 + N];
int r, c, n, t;
int find_parent(int pos){
set <pair<int,int>> :: iterator it;
it = s[norm[v[pos].x + 1]].upper_bound(make_pair(v[pos].y, 0));
return (*it).second;
}
void solve(int xi, int yi, int xf, int yf){
int r, pas;
r = 0;
pas = 1 << LOG;
while(pas){
if(r + pas <= n && (v[r + pas].x < xi || (v[r + pas].x == xi && v[r + pas].y < yi)))
r += pas;
pas >>= 1;
}
r++;
if(v[r].x != xi || (v[r].x == xi && v[r].y < yi)){
cout << "No\n";
return;
}
int stramos = xf - xi - 1;
for(int i = LOG; 0 <= i; i--)
if(stramos & (1 << i))
r = dp[i][r];
if(r > 0){
if((v[r].x == xf - 1 || v[r].x == xf) && v[r].y <= yf) cout << "Yes\n";
else cout << "No\n";
} else cout << "No\n";
}
int main() {
int cur(0);
cin >> r >> c >> n;
for(int i = 1; i <= n; i++){
cin >> v[i].x >> v[i].y;
if(norm[v[i].x] == 0)
norm[v[i].x] = ++cur;
if(!v[i].cheie)
v[i].cheie = norm[v[i].x];
}
sort(v + 1, v + n + 1);
for(int i = 1; i <= n; i++)
s[v[i].cheie].insert(make_pair(v[i].y, i));
for(int i = 1; i <= n; i++){
int pr = find_parent(i);
if(v[pr].x == v[i].x + 1 && v[pr].y >= v[i].y) // daca e in dreapta lui
dp[0][i] = pr;
}
for(int i = 1; i < LOG; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = dp[i - 1][dp[i - 1][j]];
cin >> t;
while(t--){
int xi, yi, xf, yf;
cin >> xi >> yi >> xf >> yf;
if(xf < xi || (xf == xi && yf < yi)) cout << "No\n";
else if(xf == xi && yi <= yf) cout << "Yes\n";
else solve(xi, yi, xf, yf);
}
return 0;
}