#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=5e5+5;
const int LG=20;
int n, m, q, nod[nx<<2], la[nx<<2];
vector<int> ve[nx];
vector<ii> f[nx];
string ans[nx];
void down(int id)
{
if(la[id]==-inf) return;
for(int j = id*2; j <= id*2+1; j++)
la[j]=max(la[j], la[id]), nod[j]=max(nod[j], la[id]);
la[id]=-inf;
}
void update(int id, int l, int r, int u, int v, int val)
{
if(l>v || r<u) return;
if(l>=u && r<=v)
{
la[id]=max(la[id], val);
nod[id]=max(nod[id], val);
return;
}
int mid=(l+r)>>1;
down(id);
update(id<<1, l, mid, u, v, val);
update(id<<1|1, mid+1, r, u, v, val);
nod[id]=min(nod[id<<1], nod[id<<1|1]);
}
int get(int id, int l, int r, int u, int v)
{
if(l>v || r<u) return inf;
if(l>=u && r<=v) return nod[id];
int mid=(l+r)>>1;
down(id);
return min(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m>>q;
while(m--)
{
int l, r;
cin>>l>>r;
ve[r].emplace_back(l);
}
for(int i = 1; i <= q; i++)
{
int l, r;
cin>>l>>r;
f[r].emplace_back(l, i);
}
memset(la, -0x3f, sizeof(la));
memset(nod, -0x3f, sizeof(nod));
for(int i = 1; i <= n; i++)
{
for(int x:ve[i])
update(1, 1, n, x, i, x);
for(auto it:f[i])
ans[it.se]=(get(1, 1, n, it.fi, i)>=it.fi)?"YES":"NO";
}
for(int i = 1; i <= q; i++)
cout<<ans[i]<<'\n';
}
| # | 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... |