Geome try/codechef ENC2020F

Ссылки сюда (1) →

codechef/ENC2020F

#include <bits/stdc++.h>
 
constexpr size_t DIV_CNT = 100000 + 1;
 
enum class UpdateKind {
    APPEND, DELETE,
};
 
void update_divs(uint64_t num, std::vector<uint64_t>& divs, std::set<size_t>& divs_set,
                 const std::vector<std::vector<uint64_t>>& divs_map, UpdateKind kind) {
    for (auto div : divs_map[num]) {
        switch (kind) {
            case UpdateKind::APPEND: {
                ++divs[div];
                if (divs[div] == 2) {
                    divs_set.insert(div);
                }
                break;
            }
            case UpdateKind::DELETE: {
                --divs[div];
                if (divs[div] == 1) {
                    divs_set.erase(div);
                }
                break;
            }
            default: {
                __builtin_unreachable();
            }
        }
    }
}
 
int main() {
    std::vector<std::vector<uint64_t>> divs_map(DIV_CNT);
    for (uint64_t num = 1; num < DIV_CNT; ++num) {
        for (uint64_t idx = num; idx < DIV_CNT; idx += num) {
            divs_map[idx].push_back(num);
        }
    }
 
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    size_t cnt = 0, qcnt;
    std::cin >> cnt >> qcnt;
    std::vector<uint64_t> nums(cnt);
    std::vector<uint64_t> divs(DIV_CNT);
    std::set<size_t> divs_set;
    for (auto& num : nums) {
        std::cin >> num;
        update_divs(num, divs, divs_set, divs_map, UpdateKind::APPEND);
    }
 
    std::vector<uint64_t> ans_vec;
    while (qcnt--) {
        int type = 0;
        std::cin >> type;
        switch (type) {
            case 1: {
                size_t idx = cnt;
                uint64_t curr = 0;
                std::cin >> idx >> curr;
                auto prev = nums[idx];
                nums[idx] = curr;
                update_divs(prev, divs, divs_set, divs_map, UpdateKind::DELETE);
                update_divs(curr, divs, divs_set, divs_map, UpdateKind::APPEND);
                break;
            }
            case 2: {
                uint64_t ans = (divs_set.empty() ? 1 : *std::prev(std::end(divs_set)));
                ans_vec.push_back(ans);
                break;
            }
            default: {
                __builtin_unreachable();
            }
        }
    }
 
    for (auto ans : ans_vec) {
        std::cout << ans << '\n';
    }
 
    return 0;
}

Решено: Ельчинов Егор 23:16, 12 мая 2022 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.