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;
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define popcount __builtin_popcountll
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
return l + rd() % (r - l + 1);
}
const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int inf = 1e9; // INT_MAX;
const long long llinf = 1e18; // LLONG_MAX;
template<class X, class Y>
bool minimize(X &a, Y b) {
return a > b ? (a = b, true) : false;
}
template<class X, class Y>
bool maximize(X &a, Y b) {
return a < b ? (a = b, true) : false;
}
template<class X, class Y>
bool add(X &a, Y b) {
a += b;
while (a >= mod) a -= mod;
while (a < 0) a += mod;
return true;
}
struct node {
int L, R, M, val;
int lazy = 0;
node *l, *r;
node (int _L, int _R) : L(_L), R(_R) {
M = (L + R) >> 1;
val = 0;
if (L < R) {
l = new node(L, M);
r = new node(M + 1, R);
}
}
void down() {
l->lazy = max(l->lazy, lazy);
r->lazy = max(r->lazy, lazy);
l->val = max(l->val, lazy);
r->val = max(r->val, lazy);
}
void update(int u, int v, int c) {
if (v < L || u > R) return;
if (u <= L && R <= v) {
lazy = max(lazy, c);
val = max(val, c);
return;
}
down();
l->update(u, v, c);
r->update(u, v, c);
val = min(l->val, r->val);
}
int get(int u, int v) {
if (v < L || u > R)
return inf;
if (u <= L && R <= v)
return val;
down();
return min(l->get(u, v), r->get(u, v));
}
} *root;
struct SegmentTree {
int n;
vector<int> val, lazy;
void init(int _n) {
n = _n;
val.assign(n * 4 + 5, 0);
lazy.assign(n * 4 + 5, 0);
}
void down(int i) {
for (int j = i * 2; j <= i * 2 + 1; ++j) {
val[j] = max(val[j], lazy[i]);
lazy[j] = max(lazy[j], lazy[i]);
}
}
void update(int i, int L, int R, int l, int r, int c) {
if (r < L || l > R)
return;
if (l <= L && R <= r) {
val[i] = max(val[i], c);
lazy[i] = max(lazy[i], c);
return;
}
down(i);
int M = (L + R) >> 1;
update(i << 1, L, M, l, r, c);
update(i << 1 | 1, M + 1, R, l, r, c);
val[i] = min(val[i << 1], val[i << 1 | 1]);
}
int get(int i, int L, int R, int l, int r) {
if (r < L || l > R)
return inf;
if (l <= L && R <= r)
return val[i];
down(i);
int M = (L + R) >> 1;
return min(get(i << 1, L, M, l, r),
get(i << 1 | 1, M + 1, R, l, r));
}
void update(int l, int r, int c) {
update(1, 1, n, l, r, c);
}
int get(int l, int r) {
return get(1, 1, n, l, r);
}
} t;
int n, m, q;
vector<int> curtain[N];
vector<pair<int, int> > query[N];
int ans[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= m; ++i) {
int l, r;
cin >> l >> r;
curtain[r].push_back(l);
}
for (int i = 1; i <= q; ++i) {
int s, e;
cin >> s >> e;
query[e].emplace_back(s, i);
}
t.init(n);
root = new node(1, n);
for (int r = 1; r <= n; ++ r) {
for (int l : curtain[r]) {
// root->update(l, r, l);
t.update(l, r, l);
}
for (auto [l, id] : query[r]) {
// ans[id] = root->get(l, r) >= l;
ans[id] = t.get(l, r) >= l;
}
}
for (int i = 1; i <= q; ++i)
cout << (ans[i] ? "YES" : "NO") << '\n';
// for (int i = 1; i <= n; ++i)
// cout << root->get(i, i) << ' ';
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... |