This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
vector<int> adj[MAXN];
bitset<MAXN> memo[MAXN];
bool v[MAXN];
void dp(int x) {
if(v[x]) return;
v[x] = 1;
memo[x][x] = 1;
for(int i : adj[x]) {
dp(i);
memo[x] |= memo[i];
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int r, c, n, x1, y1, x2, y2;
cin >> r >> c >> n;
pair<int, int> a[n];
for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
sort(a, a+n);
for(int i = 0; i < n-1; i++) if(a[i].first == a[i+1].first) adj[i].push_back(i+1);
map<int, set<pair<int, int>>> m;
for(int i = 0; i < n; i++) {
m[a[i].first].insert({a[i].second, i});
}
for(int i = 0; i < n; i++) {
if(m.find(a[i].first+1) == m.end()) continue;
auto it = m[a[i].first+1].lower_bound({a[i].second, 0});
if(it == m[a[i].first+1].end()) continue;
adj[i].push_back(it->second);
}
for(int i = 0; i < n; i++) dp(i);
int q;
cin >> q;
while(q--) {
cin >> x1 >> y1 >> x2 >> y2;
if(x1 == x2) {
cout << "Yes" << '\n';
continue;
}
if(m.find(x1) == m.end()) {
cout << "No" << '\n';
continue;
}
if(m.find(x2-1) == m.end()) {
cout << "No" << '\n';
continue;
}
auto it = m[x1].lower_bound({y1, 0});
auto it2 = m[x2-1].upper_bound({y2, 0});
if(it == m[x1].end()) {
cout << "No" << '\n';
continue;
}
if(it2 == m[x2-1].begin()) {
cout << "No" << '\n';
continue;
}
it2--;
if(memo[it->second][it2->second]) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
}
Compilation message (stderr)
/tmp/ccBsLSfF.o: in function `__tcf_0':
trampoline.cpp:(.text+0x9): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccBsLSfF.o
/tmp/ccBsLSfF.o: in function `dp(int) [clone .part.0]':
trampoline.cpp:(.text+0x54b): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccBsLSfF.o
/tmp/ccBsLSfF.o: in function `main':
trampoline.cpp:(.text.startup+0x38): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x3f): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x4a): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x108): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x208): relocation truncated to fit: R_X86_64_PC32 against symbol `adj' defined in .bss section in /tmp/ccBsLSfF.o
trampoline.cpp:(.text.startup+0x50e): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x546): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x5dd): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/10/libstdc++.a(globals_io.o)
trampoline.cpp:(.text.startup+0x695): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
