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 = 5e5 + 5;
int tree[maxn * 4];
int lazy[maxn * 4];
vector<int> segment[maxn];
vector<pair<int, int>> que[maxn];
int n, m, q;
bool ans[maxn];
struct segment_tree {
int n;
segment_tree() {}
segment_tree(int n) : n(n) {}
void down(int ind, int l, int r) {
tree[ind] = max(tree[ind], lazy[ind]);
if(l != r) {
lazy[ind * 2] = max(lazy[ind * 2], lazy[ind]);
lazy[ind * 2 + 1] = max(lazy[ind * 2 + 1], lazy[ind]);
}
lazy[ind] = 0;
}
void update(int ind, int l, int r, int x, int y, int val) {
if(lazy[ind]) down(ind, l, r);
if(l > y || r < x) return;
if(x <= l and r <= y) {
lazy[ind] = val;
down(ind, l, r);
return;
}
int mid = (l + r) / 2;
update(ind * 2, l, mid, x, y, val);
update(ind * 2 + 1, mid + 1, r, x, y, val);
tree[ind] = min(tree[ind * 2], tree[ind * 2 + 1]);
}
int get(int ind, int l, int r, int x, int y) {
if(lazy[ind]) down(ind, l, r);
if(l > y || r < x) return n + 1;
if(x <= l and r <= y) return tree[ind];
int mid = (l + r) / 2;
return min(get(ind * 2, l, mid, x, y), get(ind * 2 + 1, mid + 1, r, x, y));
}
void update(int x, int y, int val) {
update(1, 1, n, x, y, val);
}
int get(int x, int y) {
return get(1, 1, n, x, y);
}
} st;
void solve() {
cin >> n >> m >> q;
for(int i = 1; i <= m; ++i) {
int l, r; cin >> l >> r;
segment[r].push_back(l);
}
st = segment_tree(n);
for(int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
que[r].push_back({l, i});
}
for(int i = 1; i <= n; ++i) {
for(auto l:segment[i]) {
st.update(l, i, l);
}
for(auto e:que[i]) {
ans[e.second] = (st.get(e.first, i) >= e.first);
}
}
for(int i = 1; i <= q; ++i) {
cout << (ans[i] ? "YES\n" : "NO\n");
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |