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 ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define f first
#define s second
#define pb push_back
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
const ll maxn = 5e5+5;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;
vector<int> seg(4*maxn), tag(4*maxn);
void push(int x, int l, int r){
seg[x] = max(seg[x], tag[x]);
if (l < r){
tag[x+x] = max(tag[x], tag[x+x]);
tag[x+x+1] = max(tag[x], tag[x+x+1]);
}
tag[x] = 0;
}
int query(int l, int r, int nl, int nr, int x){
push(x, nl, nr);
if (l > nr || r < nl) return inf;
if (l <= nl && nr <= r) return seg[x];
int mid = nl+nr>>1;
return min(query(l, r, nl, mid, x+x), query(l, r, mid+1, nr, x+x+1));
}
void modify(int l, int r, int nl, int nr, int v, int x){
if (l > nr || r < nl){
push(x, nl, nr);
return;
}
if (l <= nl && nr <= r){
tag[x] = max(tag[x], v);
push(x, nl, nr);
return;
}
push(x, nl, nr);
int mid = nl+nr>>1;
modify(l, r, nl, mid, v, x+x);
modify(l, r, mid+1, nr, v, x+x+1);
seg[x] = min(seg[x+x], seg[x+x+1]);
}
int n, m, q;
bool cmp(pip a, pip b){
return a.s.s < b.s.s;
}
signed main(){
IOS();
cin>>n>>m>>q;
vector<pip> mo(m), quer(q);
vector<int> ans(q);
REP(i, m){
cin>>mo[i].s.f>>mo[i].s.s;
mo[i].f = i;
}
REP(i, q){
cin>>quer[i].s.f>>quer[i].s.s;
quer[i].f = i;
}
sort(ALL(mo), cmp); sort(ALL(quer), cmp);
int ptr = 0;
REP(i, q){
while(ptr < m && mo[ptr].s.s <= quer[i].s.s){
modify(mo[ptr].s.f, mo[ptr].s.s, 1, n, mo[ptr].s.f, 1);
ptr++;
}
if (query(quer[i].s.f, quer[i].s.s, 1, n, 1) >= quer[i].s.f){
ans[quer[i].f] = 1;
}
else ans[quer[i].f] = 0;
}
REP(i, q) cout<<(ans[i]?"YES":"NO")<<endl;
}
Compilation message (stderr)
curtains.cpp: In function 'int query(int, int, int, int, int)':
curtains.cpp:33:34: warning: overflow in conversion from 'long long int' to 'int' changes value from '1152921504606846976' to '0' [-Woverflow]
33 | if (l > nr || r < nl) return inf;
| ^~~
curtains.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = nl+nr>>1;
| ~~^~~
curtains.cpp: In function 'void modify(int, int, int, int, int, int)':
curtains.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid = nl+nr>>1;
| ~~^~~
# | 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... |