| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1145132 | saidpon | Trampoline (info1cup20_trampoline) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define nemeshay ios_base::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
#define int long long
#define sigma signed
#define pb push_back
#define fr first
#define sc second
#define pii pair<int, int>
#define double long double
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define OK cout << "OK" << endl
#define Ok cout << "Ok" << endl
#define nosolve cout << "-1" << endl
using namespace std;
const int N = 2e6 + 2, inf = 1e18 + 7, mod = 998244353;
pii a[N];
int c[N], p[N];
vector <int> pon[N];
sigma main() {
nemeshay
int R, C, n;
cin >> R >> C >> n;
map <pii, int> ladno;
map <int, int> comp, rcomp;
set <int> s;
for (int i = 0; i < n; i++) {
cin >> a[i].fr >> a[i].sc;
pon[a[i].fr].pb(a[i].sc);
s.insert(a[i].fr);
}
int compind = 0;
for (auto j: s.size()) comp[j] = compind, rcomp[compind] = j, compind++;
for (int i = 0; i < n; i++) pon[comp[a[i].fr]].pb(a[i].sc);
for (int i = 0; i < compind; i++) sort (pon[i].begin(), pon[i].end());
sort (a, a + n);
for (int i = n - 1; i >= 0; i--) {
ladno[{a[i].fr, a[i].sc}] = i;
int ind = comp[a[i].fr];
if (!ind) break;
ind--;
int up = upper_bound(pon[ind].begin(), pon[ind].end(), a[i].sc) - pon[ind].begin();
up--;
if (up == -1) continue;
p[i] = ladno[{rcomp[ind], pon[ind][up]}];
}
p[0] = -1;
for (int i = n - 1; i >= 0; i--) {
if (c[i] > -1) continue;
int x = i;
while (x > -1) c[x] = i, x = p[x];
}
int q;
cin >> q;
while (q--) {
int xs, ys, xf, yf;
cin >> xs >> ys >> xf >> yf;
if (xs == xf) {
YES;
continue;
}
xf--;
int ind1 = lower_bound(pon[xs].begin(), pon[xs].end(), ys) - pon[xs].begin();
if (ind1 == pon[xs].size()) {
NO;
continue;
}
int ind2 = upper_bound(pon[xf].begin(), pon[xf].end(), yf) - pon[xf].begin();
ind2--;
if (ind2 == -1) {
NO;
continue;
}
if (c[ladno[{xs, pon[xs][ind1]}]] == c[ladno[{xf, pon[xf][ind2]}]] || xs == xf) YES;
else NO;
}
}