CSES - Putka Open 2025 – 2/5

Submission details
Task:	Ryhmät
Sender:	jhuun
Submission time:	2025-09-28 22:20:39 +0300
Language:	C++ (C++20)
Status:	READY
Result:	10

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

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	1, 2, 3	details
#2	ACCEPTED	0.01 s	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	ACCEPTED	0.61 s	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;
        }
    }
};

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;
}

void solve(const std::vector<pi>& N, const std::vector<pi>& Kp, std::vector<bool>& used, std::size_t idx, int ki, bool& ok) {
    if (idx == Kp.size()) {
        std::cout << "YES\n";
        ok = true;
        return;
    }
    std::size_t bi = std::numeric_limits<int>::max();
    int bb = std::numeric_limits<int>::max();
    for (std::size_t i = 0; !ok && i < N.size(); ++i) {
        if (used[i]) {
            continue;
        }
        const auto [a, b] = N[i];
        if (!(a <= Kp[idx].first && b >= Kp[idx].first)) {
            continue;
        }
        if (b < bb) {
            bi = i;
            bb = b;
        }
    }
    if (bi != std::numeric_limits<int>::max()) {
        used[bi] = true;
        if (ki + 1 == Kp[idx].second) {
            solve(N, Kp, used, idx + 1, 0, ok);
        } else {
            solve(N, Kp, used, idx, ki + 1, ok);
        }
    }
}

int main() {
    int n, t;
    std::cin >> n >> t;
    std::vector<pi> N;
    std::vector<std::vector<int>> D(n + 1, std::vector<int>(n + 1));
    for (int i = 0; i < n; ++i) {
        int a, b;
        std::cin >> a >> b;
        --a;
        --b;
        N.emplace_back(a, b);
        ++D[0][a];
        --D[b + 1][a];
        --D[0][n];
        ++D[b + 1][n];
    }
    std::vector<std::vector<int>> R(n + 1, std::vector<int>(n + 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            R[i][j] = D[i][j];
            if (i > 0) {
                R[i][j] += R[i - 1][j];
            }
            if (j > 0) {
                R[i][j] += R[i][j - 1];
            }
            if (i > 0 && j > 0) {
                R[i][j] -= R[i - 1][j - 1];
            }
        }
    }
    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());
        bool ok = false;
        solve(N, Kp, used, 0, 0, ok);
        if (!ok) {
            std::cout << "NO\n";
        }
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

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

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

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

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

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

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

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

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: ACCEPTED

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

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

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

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)