oj.uz

Submission #763593

# Submission time Handle Problem Language Result Execution time Memory
763593 2023-06-22T13:37:48 Z matheuziz Fish (IOI08_fish) C++17
0 / 100
 291 ms 20072 KB 
#include <bits/stdc++.h>
#include <cstdint>
#include <cstdlib>
#include <stdint.h>

struct SegmentTree {
    std::vector<uint32_t> tree;
    uint32_t size, modulo;

    SegmentTree(uint32_t numElements, uint32_t mod) {
        size = numElements;
        modulo = mod;
        tree = std::vector<uint32_t>(2 * numElements, 1);
    }

    void update(uint32_t index, uint32_t value) {
        index += size;
        tree[index] = value % modulo;

        auto parentIndex = index;
        while (parentIndex /= 2) {
            auto sonLeftIndex = parentIndex * 2;
            auto sonRightIndex = sonLeftIndex + 1;
            tree[parentIndex] = (tree[sonLeftIndex] * tree[sonRightIndex]) % modulo;
        }
    }
    
    uint32_t range_prod(uint32_t start, uint32_t end) {
        uint32_t product = 1;
        if (end > size) return product;

        start += size;
        end += size;
    
        // Traverse the range and accumulate the product
        while (start <= end) {
            if (start & 1) {
                product = (product * tree[start]) % modulo;
                start++;
            }
            if (!(end & 1)) {
                product = (product * tree[end]) % modulo;
                end--;
            }
            start /= 2;
            end /= 2;
        }
        return product;
    }
};

uint32_t calc_combinations(
    const std::vector<std::pair<uint32_t, uint32_t>>& largest,
    const std::vector<std::pair<uint32_t, uint32_t>>& fishes,
    const std::vector<std::vector<uint32_t>>& lengthsByKind,
    const std::vector<uint32_t>& kindIndex,
    std::vector<uint32_t>& count,
    const uint32_t& modulo
) {
    /*
        largest: (2, 1) (5, 0) (8, 2)
        fishes: (2, 1) (2, 2) (4, 0) (5, 0) (8, 2)
        lengthsByKind:
            0 -> 4, 5
            1 -> 2
            2 -> 2, 8
        kindIndex:
            0 -> 1
            1 -> 0
            2 -> 2
        count: 0, 0, 0
    */
    SegmentTree tree(largest.size(), modulo);
    uint32_t fishIndex = 0;
    uint32_t answer = 0;
    for (const auto &[length, kind] : largest) {
        // Go through all fish that current can eat
        // But start from previous big fish's index
        // printf("fishIndex: %d\n", fishIndex);
        // printf("length: %d, kind: %d\n", length, kind);
        while (fishIndex < fishes.size() && 2 * fishes[fishIndex].first <= length) {
            auto &[fLen, fKind] = fishes[fishIndex];
            // printf("\t fish: (%d, %d) ", fLen, fKind);
            count[fKind]++; // How many fishes have been eaten by kind
            tree.update(kindIndex[fKind], count[fKind] + 1);
            fishIndex++;
        }
        // printf("\ncount: ");
        // for(auto e: count) {
        //     printf("%d ", e);
        // }
        // printf("\n tree*: ");
        // for(uint32_t i = tree.size; i < tree.size*2; i++) {
        //     printf("%d ", tree.tree[i]);
        // }

        // printf("\n\n");

        // Search over larger fishes of other kinds for the greatest fish that cannot
        // catch more fish of the current kind.
        uint32_t left = kindIndex[kind] + 1, right = largest.size() - 1;
        while (left <= right) {
            uint32_t mid = (left + right) / 2, eatableCount = 0;

            for (auto small : lengthsByKind[kind]) {
                if (small > largest[mid].first / 2) break;
                eatableCount++;
            }
            if (eatableCount <= count[kind]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // tree.update(kindIndex[kind], 1);

        auto combinationsForKind = /*tree.range_prod(0, left - 1) +
            (count[kind] % modulo) **/ tree.range_prod(0, kindIndex[kind]);

        answer = (answer + combinationsForKind) % modulo;

        // tree.update(kindIndex[kind], count[kind] + 1);
    }
    return answer;
}

int main() {
    uint32_t fishCount, gemCount, modulo;
    if (scanf("%u\n%u\n%u", &fishCount, &gemCount, &modulo) != 3) {
        exit(EXIT_FAILURE);
    }

    std::vector<std::pair<uint32_t, uint32_t>> fishes(fishCount), largest(gemCount, {0, 0});
    std::vector<std::vector<uint32_t>> lengthsByKind(gemCount);
    std::vector<uint32_t> kindIndex(gemCount), count(gemCount, 0);

    for (auto &[length, kind] : fishes) {
        if (scanf("%u %u", &length, &kind) != 2) {
            exit(EXIT_FAILURE);
        }
        kind--;
        largest[kind] = std::max(largest[kind], {length, kind});
    }

    std::sort(fishes.begin(), fishes.end());
    std::sort(largest.begin(), largest.end());

    for (size_t i = 0; i < largest.size(); i++) { kindIndex[largest[i].second] = i; }
    for (const auto &[length, kind] : fishes) { lengthsByKind[kind].push_back(length); }

    uint32_t answer = calc_combinations(
        largest, fishes, lengthsByKind, kindIndex, count, modulo
    );
    printf("%d\n", answer);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 123 ms 6640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 3168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 436 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 4632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 6964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4728 KB Output is correct
2 Incorrect 145 ms 14188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 7228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 151 ms 8496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 8196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 199 ms 16116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 16860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 20072 KB Output isn't correct
2 Halted 0 ms 0 KB -