Submission #1249616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249616		garrin	Curtains (NOI23_curtains)	C++20	9 / 100	1596 ms	2952 KiB

curtains

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

bool sub1(int st, int end, vector<pair<int, int>>& cur) {
    int n = end - st + 1;
    if (n > 20) return false;
    int mt = (1 << n) - 1;
    vector<int> cmask;
    for (auto& i : cur) {
        int mask = 0;
        for (int pos = max(i.first, st); pos <= min(i.second, end); pos++) {
            mask |= (1 << (pos - st));
        }
        if (mask > 0) {
            cmask.push_back(mask);
        }
    }
    vector<bool> dp(1 << n, false);
    dp[0] = true;
    for (int mask = 0; mask < (1 << n); mask++) {
        if (!dp[mask]) continue;
        for (int iMask : cmask) {
            int newMask = mask | iMask;
            dp[newMask] = true;
        }
    }
    return dp[mt];
}

bool sub2(int st, int end, vector<pair<int, int>>& cur) {
    if (st > end) return true;
    if (cur.empty()) return false;
    sort(cur.begin(), cur.end());
    int current = st;
    int i = 0;
    while (current <= end) {
        int furr = current - 1;
        while (i < cur.size() && cur[i].first <= current) {
            if (cur[i].second >= current) {
                furr = max(furr, cur[i].second);
            }
            i++;
        }
        if (furr < current) {
            return false;
        }
        current = furr + 1;
    }
    return true;
}

bool sub0(int st, int end, vector<pair<int, int>>& cur) {
    int m = cur.size();
    if (m > 15) return false;
    for (int mask = 0; mask < (1 << m); mask++) {
        vector<bool> vc(end - st + 1, false);
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                for (int pos = cur[i].first; pos <= cur[i].second; pos++) {
                    if (pos >= st && pos <= end) {
                        vc[pos - st] = true;
                    }
                }
            }
        }
        bool ktra = true;
        for (int i = 0; i < vc.size(); i++) {
            if (!vc[i]) {
                ktra = false;
                break;
            }
        }
        if (ktra) return true;
    }
    return false;
}

bool solve(int st, int end, vector<pair<int, int>>& allcur) {
    vector<pair<int, int>> vli;
    for (auto& i : allcur) {
        if (i.first >= st && i.second <= end) {
            vli.push_back(i);
        }
    }
    int side = end - st + 1;
    int numcur = vli.size();
    if (numcur <= 15 && side <= 20) {
        return sub0(st, end, vli);
    }
    if (side <= 20) {
        return sub1(st, end, vli);
    }
    return sub2(st, end, vli);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<int, int>> cur(m);
    for (int i = 0; i < m; i++) {
        cin >> cur[i].first >> cur[i].second;
    }
    for (int i = 0; i < q; i++) {
        int s, e;
        cin >> s >> e;
        cout << (solve(s, e, cur) ? "YES" : "NO") << "\n";
    }
    return 0;
}

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