CSES - Putka Open 2025 – 2/5

Submission details
Task:	Ryhmät
Sender:	jhuun
Submission time:	2025-09-28 16:51:12 +0300
Language:	C++ (C++20)
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	TIME LIMIT EXCEEDED	0
#2	TIME LIMIT EXCEEDED	0
#3	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	TIME LIMIT EXCEEDED	--	1, 2, 3	details
#2	TIME LIMIT EXCEEDED	--	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 s	1, 2, 3	details
#5	ACCEPTED	0.01 s	1, 2, 3	details
#6	TIME LIMIT EXCEEDED	--	2	details
#7	TIME LIMIT EXCEEDED	--	2	details
#8	TIME LIMIT EXCEEDED	--	2	details
#9	TIME LIMIT EXCEEDED	--	2, 3	details
#10	TIME LIMIT EXCEEDED	--	3	details
#11	TIME LIMIT EXCEEDED	--	3	details
#12	TIME LIMIT EXCEEDED	--	3	details
#13	TIME LIMIT EXCEEDED	--	3	details
#14	TIME LIMIT EXCEEDED	--	3	details
#15	TIME LIMIT EXCEEDED	--	3	details
#16	TIME LIMIT EXCEEDED	--	3	details

Code

#include <bits/stdc++.h>

using pi = std::pair<int, int>;

struct ST {
    std::vector<int> T;
    std::vector<int> L;
    int n;

    ST(int n) : T(400000), L(400000), n{n} { }

    void push(int v) {
        T[v * 2] += L[v];
        T[v * 2 + 1] += L[v];
        L[v * 2] += L[v];
        L[v * 2 + 1] += L[v];
        L[v] = 0;
    }

    void update(int v, int tl, int tr, int l, int r, int a) {
        if (l > r) {
            return;
        }
        if (l == tl && tr == r) {
            T[v] += a;
            L[v] += a;
        } else {
            push(v);
            const auto tm = (tl + tr) / 2;
            update(v * 2, tl, tm, l, std::min(r, tm), a);
            update(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, a);
            T[v] = std::min(T[v * 2], T[v * 2 + 1]);
        }
    }

    int query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return std::numeric_limits<int>::max();
        }
        if (l == tl && tr == r) {
            return T[v];
        }
        push(v);
        const auto tm = (tl + tr) / 2;
        return std::min(query(v * 2, tl, tm, l, std::min(r, tm)),
                        query(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r));
    }

    void update(int l, int r, int a) {
        update(1, 0, n - 1, l, r, a);
    }

    int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

void solve(const std::vector<pi>& N, const std::vector<int>& K, ST& st, std::vector<bool>& used, std::size_t idx, int ki, bool& ok) {
    if (idx == K.size()) {
        std::cout << "YES\n";
        ok = true;
        return;
    }
    for (std::size_t i = 0; !ok && i < N.size(); ++i) {
        if (!used[i]) {
            const auto [a, b] = N[i];
            if (!(a + 1 <= K[idx] && b + 1 >= K[idx])) {
                continue;
            }
            if (st.query(a, b) == 0) {
                continue;
            }
            used[i] = true;
            st.update(a, b, -1);
            if (ki + 1 == K[idx]) {
                solve(N, K, st, used, idx + 1, 0, ok);
            } else {
                solve(N, K, st, used, idx, ki + 1, ok);
            }
            st.update(a, b, 1);
            used[i] = false;
        }
    }
}

bool init_check(ST& st, std::map<int, int>& Ks) {
    for (const auto [k, ks] : Ks) {
        if (st.query(k - 1, k - 1) < k) {
            return false;
        }
    }
    return true;
}

int main() {
    int n, t;
    std::cin >> n >> t;
    std::vector<pi> N;
    ST st(n);
    for (int i = 0; i < n; ++i) {
        int a, b;
        std::cin >> a >> b;
        N.emplace_back(a - 1, b - 1);
        st.update(a - 1, b - 1, 1);
    }
    std::sort(N.begin(), N.end(), [](const auto& a, const auto& b) { return (a.second - a.first) < (b.second - b.first); });
    for (int i = 0; i < t; ++i) {
        int m;
        std::cin >> m;
        std::vector<int> K(m);
        std::map<int, int> Ks;
        int ks = 0;
        for (auto& k : K) {
            std::cin >> k;
            ++Ks[k];
            ks += k;
        }
        if (ks > n) {
            std::cout << "NO\n";
        } else if (!init_check(st, Ks)) {
            std::cout << "NO\n";
        } else {
            std::sort(K.begin(), K.end());
            std::vector<bool> used(N.size());
            bool ok = false;
            solve(N, K, st, used, 0, 0, ok);
            if (!ok) {
                std::cout << "NO\n";
            }
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`100 100 10 10 10 10 6 9 6 8 ...` view save

correct output
`YES YES YES NO YES ...` view save

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`100 100 9 9 6 10 8 10 8 8 ...` view save

correct output
`NO YES NO YES NO ...` view save

user output
(empty)

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 1 1 1 1 1 1 1 1 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 100 100 100 100 100 100 100 100 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
`YES YES YES YES YES ...` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`100 100 4 9 3 8 7 9 7 9 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
`NO NO NO NO NO ...` view save

Test 6

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 9 10 2 5 10 10 5 5 ...` view save

correct output
`YES YES YES YES NO ...` view save

user output
(empty)

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 5 7 9 9 3 7 8 10 ...` view save

correct output
`YES NO NO YES YES ...` view save

user output
(empty)

Test 8

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 1 1 1 1 1 1 1 1 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
(empty)

Test 9

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
(empty)

Test 10

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 1000 774 778 363 852 309 668 261 459 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
(empty)

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 1000 1233 1914 901 3963 1277 4293 1083 1599 ...` view save

correct output
`NO NO YES NO NO ...` view save

user output
(empty)

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 1000 1970 8631 4606 5797 6317 8162 8204 8789 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
(empty)

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 1000 1000 1000 1000 1000 1000 1000 1000 1000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
(empty)

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 100000 1 100000 1 100000 1 100000 1 100000 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
(empty)

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 100000 80971 98445 93046 96043 74840 94035 95931 96609 ...` view save

correct output
`NO NO NO NO NO ...` view save

user output
(empty)

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 10000 6481 14350 69129 87600 6217 16462 4387 16625 ...` view save

correct output
`YES YES YES YES YES ...` view save

user output
(empty)

Putka Open 2025 – 2/5

Ryhmät

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Tasks

Submissions (jhuun)