CSES - Putka Open 2025 – 2/5

Submission details
Task:	Ryhmät
Sender:	jhuun
Submission time:	2025-09-28 20:43:19 +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.02 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	RUNTIME ERROR	0.39 s	3	details
#11	RUNTIME ERROR	0.39 s	3	details
#12	RUNTIME ERROR	0.39 s	3	details
#13	RUNTIME ERROR	0.39 s	3	details
#14	RUNTIME ERROR	0.39 s	3	details
#15	RUNTIME ERROR	0.39 s	3	details
#16	RUNTIME ERROR	0.39 s	3	details

Code

#include <bits/stdc++.h>

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

struct FT {
    std::vector<int> B;
    int n;

    FT(int n) : B(n), n(n) { }

    int sum(int r) const {
        int res = 0;
        for (; r >= 0; r &= r + 1, --r) {
            res += B[r];
        }
        return res;
    }

    int sum(int l, int r) const {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int d) {
        for (; idx < n; idx |= (idx + 1)) {
            B[idx] += d;
        }
    }
};

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

std::vector<pi> pre_fill(const std::vector<pi>& N, std::vector<pi>& Kp, ST& st, ST& st2, std::vector<bool>& used) {
    std::vector<pi> filled;
    for (std::size_t i = 0; i < Kp.size(); ++i) {
        auto& [k, c] = Kp[i];
        const auto la = i == 0 ? 0 : Kp[i - 1].first;
        const auto lb = i == Kp.size() - 1 ? std::numeric_limits<int>::max() : Kp[i + 1].first;
        for (std::size_t j = 0; j < N.size(); ++j) {
            if (used[j]) {
                continue;
            }
            const auto [a, b] = N[j];
            if (a > la && b < lb) {
                st.update(a, b, -1);
                st2.update(a, b, 1);
                used[j] = true;
                --c;
                filled.emplace_back(a, b);
                break;
            }
        }
    }
    return filled;
}

bool next_check(ST& st2, const std::vector<pi>& Kp, int n) {
    for (std::size_t i = 0; i < Kp.size(); ++i) {
        const auto [k, c] = Kp[i];
        const auto la = i == 0 ? 0 : Kp[i - 1].first;
        const auto ca = i == 0 ? 0 : Kp[i - 1].second;
        const auto lb = i == Kp.size() - 1 ? n : Kp[i + 1].first;
        const auto cb = i == Kp.size() - 1 ? 0 : Kp[i + 1].second;
        if (-st2.query(la, k) < c + ca && -st2.query(k, lb) < c + cb) {
            return false;
        }
    }
    return true;
}

void add_back(const std::vector<pi>& filled, ST& st, ST& st2) {
    for (const auto& [a, b] : filled) {
        st.update(a, b, 1);
        st2.update(a, b, -1);
    }
}

bool k_check(const std::vector<pi>& Kp, const FT& ft, const std::vector<std::vector<int>>& R) {
    for (std::size_t i = 0; i < Kp.size(); ++i) {
        const auto ki = Kp[i].first;
        for (std::size_t j = i; j < Kp.size(); ++j) {
            const auto kj = Kp[j].first;
            if (R[ki][kj] < ft.sum(ki, kj)) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int n, t;
    std::cin >> n >> t;
    std::vector<pi> N;
    ST st(n), st2(n);
    std::vector<std::vector<int>> R(n, std::vector<int>(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);
        st2.update(a - 1, b - 1, -1);
        for (int j = 0; j <= b - 1; ++j) {
            for (int k = a - 1; k < n; ++k) {
                ++R[j][k];
            }
        }
    }
    std::sort(N.begin(), N.end());
    for (int i = 0; i < t; ++i) {
        int m;
        std::cin >> m;
        std::vector<int> K(m);
        int ks = 0;
        for (auto& k : K) {
            std::cin >> k;
            ks += k;
        }
        if (ks > n) {
            std::cout << "NO\n";
            continue;
        }
        std::sort(K.begin(), K.end());
        std::vector<pi> Kp{{K.front() - 1, K.front()}};
        for (auto j = 1; j < m; ++j) {
            if (K[j] == K[j - 1] - 1) {
                Kp.back().second += K[j];
            } else {
                Kp.emplace_back(K[j] - 1, K[j]);
            }
        }
        FT ft(n);
        for (const auto& [k, c] : Kp) {
            ft.add(k, c);
        }
        if (!k_check(Kp, ft, R)) {
            std::cout << "NO\n";
            continue;
        }
        std::vector<bool> used(N.size());
        const auto filled = pre_fill(N, Kp, st, st2, used);
        if (!next_check(st2, Kp, n - 1)) {
            std::cout << "NO\n";
        } else {
            bool ok = false;
            solve(N, Kp, st, used, 0, 0, ok);
            if (!ok) {
                std::cout << "NO\n";
            }
        }
        add_back(filled, st, st2);
    }
}

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 ...` Truncated

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 ...` Truncated

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 ...` Truncated

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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)