Submission #55043631

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/lazysegtree>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;

    const std::vector<std::pair<Num, Num>> dyxs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    template<typename T>
    void print_oneline(const std::vector<T>& vec, std::ostream& os) {
        const auto size = vec.size();
        for(size_t i{0}; i<size; ++i) {
            os << vec.at(i) << (((i+1) == size) ? '\n' : ' ');
        }
    }

    template<typename T>
    void print_each(const std::vector<T>& vec, std::ostream& os) {
        const auto size = vec.size();
        for(size_t i{0}; i<size; ++i) {
            os << vec.at(i) << '\n';
        }
    }
}

Num func_operate(Num a, Num b) {
    return a+b;
}

Num func_unit() {
    return 0;
}

Num func_map(Num a, Num b) {
    return a + b;
}

Num func_compose(Num a, Num b) {
    return a + b;
}

Num func_id() {
    return 0;
}

void solve(std::istream& is, std::ostream& os) {
    Num n,m;
    is >> n >> m;

    std::vector<Vec> colors(m);
    for(Num i{0}; i<n; ++i) {
        Num a,b;
        is >> a >> b;
        --a;
        --b;
        colors.at(a).push_back(i);
        colors.at(b).push_back(i);
    }

    Vec ans(m+1);
    std::map<Num,Num> tbl;
    Num right {-1};

    atcoder::lazy_segtree<Num, func_operate, func_unit, Num, func_map, func_compose, func_id> tree(m+1);
    for(Num left {0}; left < m; ++left) {
        if (left > 0) {
            for(const auto& v : colors.at(left-1)) {
                tbl[v] -= 1;
                if (tbl[v] == 0) {
                    tbl.erase(v);
                }
            }
        }

        while(right < m) {
            if (tbl.size() == n) {
                Num min_w = right - left + 1;
                Num max_w = m - left;
                tree.apply(min_w, max_w + 1, 1);
                break;
            } else {
                ++right;
                if (right < m) {
                    for(const auto& v : colors.at(right)) {
                        tbl[v] += 1;
                    }
                }
            }
        }
    }

    for(Num i{1}; i<=m; ++i) {
        os << tree.prod(i,i+1) << ((i==m) ? '\n' : ' ');
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(std::istream&, std::ostream&)’:
Main.cpp:88:28: warning: comparison of integer expressions of different signedness: ‘std::map<long long int, long long int>::size_type’ {aka ‘long unsigned int’} and ‘{anonymous}::Num’ {aka ‘long long int’} [-Wsign-compare]
   88 |             if (tbl.size() == n) {
      |                 ~~~~~~~~~~~^~~~

Judge Result