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>
#define x first
#define y second
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
const int N = 200100;
const int oo = 2e9;
int n, t, nxt[N][22];
map<int, set<ii>> mp;
vector<ii> v, u;
vector<iii> gr;
ii q[N];
bool proc(int u, int v, int x, int y) {
if (u == x && v <= y) return 1;
int len = (x - u + 1);
if (!mp.count(u)) return 0;
auto it = mp[u].lower_bound(ii(v, -1));
if (it == mp[u].end()) return 0;
int cur = it->y;
for (int i = 21; i >= 0; --i) if (len >= (1 << i)) {
len -= (1 << i);
cur = nxt[cur][i];
if (cur == oo) return 0;
}
return q[cur].y <= y;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> n >> n;
for (int a, b, i = 1; i <= n; ++i) {
cin >> a >> b;
q[i] = ii(a, b);
mp[a].insert(ii(b, i));
gr.push_back(iii(ii(a, b), i));
}
sort(gr.begin(), gr.end());
int pre = oo;
for (int i = n - 1; i >= 0; --i) {
int a = gr[i].x.x, b = gr[i].x.y, id = gr[i].y;
nxt[i][0] = oo;
if (a + 1 == pre) {
v = u;
u.clear();
} else if (a < pre) {
v.clear();
u.clear();
}
if (!v.empty()) {
auto it = lower_bound(v.begin(), v.end(), ii(b, -1));
if (it != v.end()) {
nxt[i][0] = it->y;
}
}
u.push_back(ii(b, id));
pre = a;
}
for (int j = 1; j < 22; ++j) {
for (int i = 1; i <= n; ++i) if (nxt[i][j - 1] != oo) {
nxt[i][j] = nxt[ nxt[i][j - 1] ][j - 1];
}
}
cin >> t;
for (int u, v, x, y, i = 1; i <= t; ++i) {
cin >> u >> v >> x >> y;
if (proc(u, v, x, y)) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |