This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* author : bo may can 5 */
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
#define file(name) \
if(fopen(name".inp", "r")) \
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
const int MAX = 1e5 + 5;
int n, m, q;
vector <pair <int, int>> queries[MAX];
vector <int> events[MAX];
int ans[MAX], it[MAX << 2], lazy[MAX << 2];
void down(int idx) {
if(lazy[idx] == 0) return;
for (int i = 2 * idx; i <= 2 * idx + 1; ++i) {
it[i] = max(it[i], lazy[idx]);
lazy[i] = max(lazy[i], lazy[idx]);
}
lazy[idx] = 0;
}
void update(int idx, int l, int r, int u, int v, int val) {
if(l > v || r < u) return;
if(l >= u && r <= v) {
it[idx] = max(it[idx], val);
lazy[idx] = val;
return;
}
down(idx);
int mid = l + r >> 1;
update(idx << 1, l, mid, u, v, val);
update(idx << 1 | 1, mid + 1, r, u, v, val);
it[idx] = min(it[idx << 1], it[idx << 1 | 1]);
}
int get(int idx, int l, int r, int u, int v) {
if(l > v || r < u) return 1e9;
if(l >= u && r <= v) return it[idx];
down(idx);
int mid = l + r >> 1;
return min(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}
void you_make_it(void) {
cin >> n >> m >> q;
for (int i = 1; i <= m; ++i) {
int l, r; cin >> l >> r;
events[r].emplace_back(l);
}
for (int i = 1; i <= q; ++i) {
int l, r; cin >> l >> r;
queries[r].emplace_back(l, i);
}
for (int r = 1; r <= n; ++r) {
for (auto l : events[r]) update(1, 1, n, l, r, l);
for (auto [l, i] : queries[r]) {
if(get(1, 1, n, l, r) >= l) ans[i] = 1;
}
}
for (int i = 1; i <= q; ++i) cout << (ans[i] ? "YES\n" : "NO\n");
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
file("curtains");
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message (stderr)
curtains.cpp: In function 'void update(int, int, int, int, int, int)':
curtains.cpp:41:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = l + r >> 1;
| ~~^~~
curtains.cpp: In function 'int get(int, int, int, int, int)':
curtains.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = l + r >> 1;
| ~~^~~
curtains.cpp: In function 'int main()':
curtains.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:86:5: note: in expansion of macro 'file'
86 | file("curtains");
| ^~~~
curtains.cpp:12:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:86:5: note: in expansion of macro 'file'
86 | file("curtains");
| ^~~~
# | 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... |