Submission #1299926

#TimeUsernameProblemLanguageResultExecution timeMemory
1299926danglayloi1Curtains (NOI23_curtains)C++20
100 / 100
861 ms82412 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...