Submission #1160737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160737		12345678	Curtains (NOI23_curtains)	C++20	0 / 100	23 ms	47432 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, m, q, dp[nx], l, r, st[nx], ed[nx], res[nx];
set<int> sr[nx], sl[nx];
vector<int> v;

struct maxsegtree
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l||qr<ql) return 0;
        if (ql<=l&&r<=qr) return 0;
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} smx;

struct minsegtree
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l||qr<ql) return n+1;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} smn;

void solve(int l, int r, vector<int> &cur)
{
    if (cur.empty()) return;
    int md=(l+r)/2;
    vector<int> qrs, ql, qr;
    if (l!=r)
    {
        for (auto idx:cur)
        {
            if (ed[idx]<=md) ql.push_back(idx);
            else if (st[idx]>=md+1) qr.push_back(idx);
            else qrs.push_back(idx);
        }
        solve(l, md, ql);
        solve(md+1, r, qr);
    }
    else qrs=cur;
    for (int i=md+1; i<=r; i++)
    {
        dp[i]=0;
        auto itr=sr[i].upper_bound(md+1);
        if (itr!=sr[i].begin()) dp[i]=*prev(itr);
        if (itr!=sr[i].end()) dp[i]=max(dp[i], smx.query(1, n, 1, (*itr)-1, i-1));
        smx.update(1, n, 1, i, dp[i]);
    }
    for (int i=md; i>=l; i--)
    {
        dp[i]=n+1;
        auto itr=sl[i].lower_bound(md);
        if (itr!=sl[i].end()) dp[i]=*itr;
        if (itr!=sl[i].begin()) dp[i]=min(dp[i], smn.query(1, n, 1, i+1, (*prev(itr))+1));
        //cout<<"update "<<i<<' '<<dp[i]<<'\n';
        smn.update(1, n, 1, i, dp[i]);
    }
    /*
    cout<<"debug "<<l<<' '<<r<<' '<<md<<'\n';
    cout<<"l ";
    for (int i=l; i<=md; i++) cout<<dp[i]<<' ';
    cout<<'\n';
    cout<<"r ";
    for (int i=md+1; i<=r; i++) cout<<dp[i]<<' ';
    cout<<'\n';
    */
    for (auto idx:qrs) res[idx]=(dp[st[idx]]<=ed[idx]&&st[idx]<=dp[ed[idx]]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=m; i++) cin>>l>>r, sr[r].insert(l), sl[l].insert(r);
    for (int i=1; i<=q; i++) cin>>st[i]>>ed[i], v.push_back(i);
    solve(1, n, v);
    for (int i=1; i<=q; i++) cout<<(res[i]?"YES\n":"NO\n");
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20