Submission #1160760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160760		12345678	Curtains (NOI23_curtains)	C++20	100 / 100	710 ms	244556 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5, kx=20;

int n, m, q, dp[nx], l, r, st[nx], ed[nx], res[nx], layer[nx], val[nx][kx], pv[nx][kx], idx, sz, single[nx];
vector<int> sl[nx], sr[nx], upperr[nx], lowerl[nx], v;

void precompute(int l, int r, int lvl)
{
    if (l==r) return;
    int md=(l+r)/2;
    layer[md]=lvl;
    precompute(l, md, lvl+1), precompute(md+1, r, lvl+1);
    for (int i=md+1; i<=r; i++) upperr[i].push_back(md+1);
    for (int i=md; i>=l; i--) lowerl[i].push_back(md);
}

void solve(int l, int r, vector<int> &cur)
{
    if (cur.empty()) return;
    if (l==r)
    {
        for (auto idx:cur) res[idx]=single[l];
        return;
    }
    int md=(l+r)/2;
    vector<int> qrs, ql, qr;
    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);
    stack<int> s;
    //cout<<"debug "<<l<<' '<<md<<' '<<r<<'\n';
    for (int i=md+1; i<=r; i++)
    {
        //cout<<"upperbound "<<md+1<<'('<<i<<')'<<" : "<<val[i][layer[md]]<<' '<<pv[i][layer[md]]<<'\n';
        dp[i]=0;
        if (pv[i][layer[md]]!=-1) dp[i]=pv[i][layer[md]];
        if (val[i][layer[md]]!=-1) while (!s.empty()&&s.top()>=val[i][layer[md]]-1) dp[i]=max(dp[i], dp[s.top()]), s.pop();
        s.push(i);
        //cout<<"dp "<<dp[i]<<'\n';
    }
    while (!s.empty()) s.pop();
    for (int i=md; i>=l; i--)
    {
        //cout<<"lowerbound "<<md+1<<'('<<i<<')'<<" : "<<val[i][layer[md]]<<' '<<pv[i][layer[md]]<<'\n';
        dp[i]=n+1;
        if (val[i][layer[md]]!=-1) dp[i]=val[i][layer[md]]; 
        if (pv[i][layer[md]]!=-1) while (!s.empty()&&s.top()<=pv[i][layer[md]]+1) dp[i]=min(dp[i], dp[s.top()]), s.pop();
        s.push(i);
        //cout<<"dp "<<dp[i]<<'\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].push_back(l), sl[l].push_back(r), single[l]=(single[l]|(l==r));
    for (int i=1; i<=q; i++) cin>>st[i]>>ed[i], v.push_back(i);
    precompute(1, n, 0);
    /*
    cout<<"layer ";
    for (int i=1; i<=n; i++) cout<<layer[i]<<' ';
    cout<<'\n';
    */
    for (int i=1; i<=n; i++)
    {
        reverse(upperr[i].begin(), upperr[i].end());
        sort(sr[i].begin(), sr[i].end());
        sort(sl[i].begin(), sl[i].end());
        idx=0, sz=sr[i].size();
        for (auto x:upperr[i])
        {
            while (idx<sz&&x>=sr[i][idx]) idx++;
            if (idx<sz) val[i][layer[x-1]]=sr[i][idx];
            else val[i][layer[x-1]]=-1;
            if (idx>0) pv[i][layer[x-1]]=sr[i][idx-1];
            else pv[i][layer[x-1]]=-1;
        }
        idx=0, sz=sl[i].size();
        for (auto x:lowerl[i])
        {
            while (idx<sz&&x>sl[i][idx]) idx++;
            if (idx<sz) val[i][layer[x]]=sl[i][idx];
            else val[i][layer[x]]=-1;
            if (idx>0) pv[i][layer[x]]=sl[i][idx-1];
            else pv[i][layer[x]]=-1;
        }
        /*
        cout<<"upperr "<<i<<':';
        for (auto x:upperr[i]) cout<<x<<' ';
        cout<<'\n';
        cout<<"lowerl "<<i<<':';
        for (auto x:lowerl[i]) cout<<x<<' ';
        cout<<'\n';
        */
    }
    solve(1, n, v);
    for (int i=1; i<=q; i++) cout<<(res[i]?"YES\n":"NO\n");
}

/*
10 2 1
4 6
7 8
4 8
*/

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