제출 #1160556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160556		12345678	Curtains (NOI23_curtains)	C++20	24 / 100	478 ms	37080 KiB

curtains

#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int n, m, q, dp[nx][nx], l, r, mn[nx], lst;
set<int> s[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<=n; i++) mn[i]=1e9;
    for (int i=1; i<=m; i++) cin>>l>>r, s[r].insert(l), mn[l]=min(mn[l], r);
    for (int st=1; st<=n; st++)
    {
        if (mn[st]<=n) dp[st][mn[st]]=1;
        lst=mn[st];
        for (int i=mn[st]+1; i<=n; i++)
        {
            auto itr=s[i].lower_bound(st);
            if (itr!=s[i].end()&&*itr<=lst+1)
            {
                lst=i;
                dp[st][i]=1;
            }
        }
    }
    while (q--)
    {
        cin>>l>>r;
        if (dp[l][r]) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

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