Submission #893838

#	Time	Username	Problem	Language	Result	Execution time	Memory
893838		kh0i	Curtains (NOI23_curtains)	C++17	44 / 100	236 ms	55244 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 5e5 + 3;

int n, m, q;
pair<int, int> a[N], d[N];

namespace Sub12{
    bool valid_input(){ return n <= 2000 and m <= 2000 and q <= 2000; }
    void solve(){
        for(int i = 1; i <= q; ++i){
            vector<int> ck(n + 2, 0);
            for(int j = 1; j <= m; ++j){
                if(d[i].first <= a[j].first and a[j].second <= d[i].second)
                    ++ck[a[j].first], --ck[a[j].second + 1];
            }
            for(int j = 1; j <= n; ++j)
                ck[j] += ck[j - 1];
            bool ok = 1;
            for(int j = d[i].first; j <= d[i].second; ++j)
                ok &= (ck[j] > 0);
            cout << (ok ? "YES\n" : "NO\n");
        }
    }
}

namespace Sub3{
    bool valid_input(){ return n <= 2000; }

    bool has[2003][2003], ok[2003][2003];
    int p[2003][2003];

    void solve(){
        for(int i = 1; i <= m; ++i){
            has[a[i].first][a[i].second] = 1;
            p[a[i].first][a[i].second] = 1;
        }
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= i; ++j)
                p[j][i] += p[j - 1][i];
        for(int i = 1; i <= n; ++i){
            int cur = i - 1;
            for(int j = i; j <= n; ++j){
                if(has[i][j])
                    ok[i][j] = 1;
                else
                    ok[i][j] = (cur >= i ? p[cur + 1][j] - p[i - 1][j] : 0);
                cur = (ok[i][j] ? j : cur);
            }
        }
        for(int i = 1; i <= q; ++i)
            cout << (ok[d[i].first][d[i].second] ? "YES\n" : "NO\n");
    }
}

namespace Sub4{
    bool valid_input(){
        bool ok = 1;
        for(int i = 1; i <= q; ++i)
            ok &= (d[i].first == 1);
        return ok;
    }

    bool has[N], f[N];
    vector<int> rv[N];

    void solve(){
        for(int i = 1; i <= m; ++i){
            if(a[i].first == 1)
                has[a[i].second] = 1;
            rv[a[i].second].push_back(i);
        }
        int cur = 0;
        for(int i = 1; i <= n; ++i){
            if(has[i])
                f[i] = 1;
            else{
                for(int x : rv[i])
                    f[i] |= (a[x].first <= cur);
            }
            if(f[i])
                cur = i + 1;
        }
        for(int i = 1; i <= q; ++i)
            cout << (f[d[i].second] ? "YES\n" : "NO\n");
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i)
        cin >> a[i].first >> a[i].second;
    for(int i = 1; i <= q; ++i)
        cin >> d[i].first >> d[i].second;

    if(Sub12::valid_input())
        Sub12::solve();
    else if(Sub3::valid_input())
        Sub3::solve();
    else if(Sub4::valid_input())
        Sub4::solve();


    return 0;
}

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