#947611 (C++23) No.60 魔法少女

提出ソース

結果

問題	No.60 魔法少女
ユーザー	reika727
提出日時	2024-02-03 10:19:10
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	198 ms / 5,000 ms
コード長	7,385 bytes
コンパイル時間	3,552 ms
コンパイル使用メモリ	257,940 KB
実行使用メモリ	21,440 KB
最終ジャッジ日時	2024-09-28 10:45:30
合計ジャッジ時間	5,252 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	13 ms 19,200 KB
testcase_01	AC	15 ms 19,072 KB
testcase_02	AC	15 ms 19,200 KB
testcase_03	AC	15 ms 19,200 KB
testcase_04	AC	125 ms 19,456 KB
testcase_05	AC	120 ms 21,220 KB
testcase_06	AC	190 ms 21,248 KB
testcase_07	AC	159 ms 20,608 KB
testcase_08	AC	96 ms 20,352 KB
testcase_09	AC	49 ms 19,456 KB
testcase_10	AC	180 ms 21,248 KB
testcase_11	AC	31 ms 19,584 KB
testcase_12	AC	87 ms 20,608 KB
testcase_13	AC	198 ms 21,440 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'int main()':
main.cpp:251:18: warning: narrowing conversion of 'y' from 'll' {aka 'long long int'} to 'long unsigned int' [-Wnarrowing]
  251 |                 {y,x},
      |                  ^
main.cpp:251:20: warning: narrowing conversion of 'x' from 'll' {aka 'long long int'} to 'long unsigned int' [-Wnarrowing]
  251 |                 {y,x},
      |                    ^
main.cpp:252:26: warning: narrowing conversion of '(long long int)std::min<long long int>(((y + h) + 1), 1001)' from 'long long int' to 'long unsigned int' [-Wnarrowing]
  252 |                 {std::min(y+h+1,1001ll),std::min(x+w+1,1001ll)}
      |                  ~~~~~~~~^~~~~~~~~~~~~~
main.cpp:252:49: warning: narrowing conversion of '(long long int)std::min<long long int>(((x + w) + 1), 1001)' from 'long long int' to 'long unsigned int' [-Wnarrowing]
  252 |                 {std::min(y+h+1,1001ll),std::min(x+w+1,1001ll)}
      |                                         ~~~~~~~~^~~~~~~~~~~~~~

ソースコード

raw source code

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<class T=ll>inline T in(istream&is=cin){return*istream_iterator<T>(is);}
template<class T=ll,template<class,class>class Container=vector,template<class>class Allocator=allocator>inline Container<T,Allocator<T>>ins(istream&is=cin){return{istream_iterator<T>(is),istream_iterator<T>()};}
template<class Container>concept pushbackable=requires(Container&c){c.push_back(declval<typename Container::value_type>());};
template<class Container>concept reservable=requires(Container&c){c.reserve();};
template<class T=ll,template<class,class>class Container=vector,template<class>class Allocator=allocator>requires pushbackable<Container<T,Allocator<T>>>inline Container<T,Allocator<T>>ins(size_t n,istream&is=cin){Container<T,Allocator<T>>c;if constexpr(reservable<decltype(c)>)c.reserve(n);copy_n(istream_iterator<T>(is),n,back_inserter(c));return c;}
template<class T>inline bool chmin(T&a,T b){return a>b?a=b,true:false;}
template<class T>inline bool chmax(T&a,T b){return a<b?a=b,true:false;}
template<class T,class...Sizes>inline auto multdim_vector_v(T v,size_t size,Sizes...sizes){if constexpr(sizeof...(Sizes)==0)return vector(size,v);else return vector(size,multdim_vector_v(v,sizes...));}
template<class T,class...Sizes>inline auto multdim_vector(Sizes...sizes){return multdim_vector_v(T{},sizes...);}

template <class T, size_t Dimension>
class imos : protected std::vector<imos<T, Dimension - 1>> {
    friend imos<T, Dimension + 1>;

public:
    using coordinate = std::array<std::size_t, Dimension>;

    struct segment {
        coordinate begin, end;
    };

    constexpr inline static std::size_t dimension = Dimension;

protected:
    T& get(const std::span<const std::size_t, Dimension> idxs)
    {
        return (*this)[idxs.front()].get(idxs.template last<Dimension - 1>());
    }

    void set(
        const std::span<const std::size_t, Dimension> begin,
        const std::span<const std::size_t, Dimension> end,
        const T weight
    )
    {
        (*this)[begin.front()].set(
            begin.template last<Dimension - 1>(),
            end.template last<Dimension - 1>(),
            weight
        );
        (*this)[end.front()].set(
            begin.template last<Dimension - 1>(),
            end.template last<Dimension - 1>(),
            -weight
        );
    }

    imos<T, Dimension> &operator+=(const imos<T, Dimension> &ci)
    {
        for (std::size_t i = 0; i < this->size(); ++i) {
            (*this)[i] += ci[i];
        }
        return *this;
    }

public:
    using std::vector<imos<T, Dimension - 1>>::begin;
    using std::vector<imos<T, Dimension - 1>>::end;
    using std::vector<imos<T, Dimension - 1>>::operator[];

    template <class... Sizes>
    imos(const std::size_t size, const Sizes... sizes)
        : std::vector<imos<T, Dimension - 1>>(
              size + 1,
              imos<T, sizeof...(Sizes)>(sizes...)
          )
    {
    }

    T& get(const coordinate &c)
    {
        return get(std::span{c});
    }

    void set(const segment &s, const T weight)
    {
        set(std::span{s.begin}, std::span{s.end}, weight);
    }

    void accumulate()
    {
        for (std::size_t i = 0; i < this->size() - 1; ++i) {
            (*this)[i + 1] += (*this)[i];
        }
        for (auto &child : *this) {
            child.accumulate();
        }
    }
};

template <class T>
class imos<T, 1> : protected std::vector<T> {
    friend imos<T, 2>;

public:
    using coordinate = std::array<std::size_t, 1>;

    struct segment {
        coordinate begin, end;
    };

    constexpr inline static std::size_t dimension = 1;

private:
    T& get(const std::span<const std::size_t, 1> idxs)
    {
        return (*this)[idxs.front()];
    }

    void set(
        const std::span<const std::size_t, 1> begin,
        const std::span<const std::size_t, 1> end,
        const T weight
    )
    {
        (*this)[begin.front()] += weight;
        (*this)[end.front()] -= weight;
    }

    imos<T, 1> &operator+=(const imos<T, 1> &ci)
    {
        for (std::size_t i = 0; i < this->size(); ++i) {
            (*this)[i] += ci[i];
        }
        return *this;
    }

public:
    using std::vector<T>::begin;
    using std::vector<T>::end;
    using std::vector<T>::operator[];

    explicit imos(const std::size_t size)
        : std::vector<T>(size + 1)
    {
    }

    T& get(const coordinate &c)
    {
        return (*this)[c.front()];
    }

    T& get(const std::size_t idx)
    {
        return (*this)[idx];
    }

    void set(const segment &s, const T weight)
    {
        set(std::span{s.begin}, std::span{s.end}, weight);
    }

    void set(const size_t begin, const size_t end, const T weight)
    {
        set({.begin = begin, .end = end}, weight);
    }

    void accumulate()
    {
        for (std::size_t i = 0; i < this->size() - 1; ++i) {
            (*this)[i + 1] += (*this)[i];
        }
    }
};

template <class T, size_t Dimension>
class cyclic_imos final : public imos<T, Dimension> {
public:
    using typename imos<T, Dimension>::segment;
    using imos<T, Dimension>::imos;

    void set_cyclic(const segment &s, const T weight)
    {
        this->set(s, weight);
        for (unsigned i = 1; i < (1 << Dimension); ++i) {
            segment correction;
            for (unsigned j = 0; j < Dimension; ++j) {
                if (i & (1 << j)) {
                    if (s.begin[j] <= s.end[j]) {
                        goto CONTINUE;
                    }
                    correction.begin[j] = 0;
                    correction.end[j] = this->size() - 1;
                } else {
                    correction.begin[j] = s.begin[j];
                    correction.end[j] = s.end[j];
                }
            }
            this->set(correction, weight);
        CONTINUE:
            ;
        }
    }
};

template <class T>
class cyclic_imos<T, 1> final : public imos<T, 1> {
public:
    using typename imos<T, 1>::segment;
    using imos<T, 1>::imos;

    void set_cyclic(const segment &s, const T weight)
    {
        this->set(s, weight);
        if (s.begin.front() > s.end.front()) {
            (*this).front() += weight;
            (*this).back() -= weight;
        }
    }

    void set_cyclic(const std::size_t begin, const std::size_t end, const T weight)
    {
        set_cyclic({.begin = begin, .end = end}, weight);
    }
};

template <class T>
auto make_imos(auto... sizes)
{
    return imos<T, sizeof...(sizes)>(sizes...);
}

template <class T>
auto make_cyclic_imos(auto... sizes)
{
    return cyclic_imos<T, sizeof...(sizes)>(sizes...);
}

int main()
{
    struct enemy{
        ll x,y,hp;
    };

    ll n=in(),k=in();
    vector<enemy>enemies(n);
    for(ll i=0;i<n;++i){
        ll x=in(),y=in(),hp=in();
        enemies[i]={x+500,y+500,hp};
    }
    auto imos=make_cyclic_imos<ll>(1002,1002);
    for(ll i=0;i<k;++i){
        ll x=in(),y=in(),w=in(),h=in(),d=in();
        x+=500;
        y+=500;
        imos.set(
            {
                {y,x},
                {std::min(y+h+1,1001ll),std::min(x+w+1,1001ll)}
            },
            d
        );
    }
    imos.accumulate();
    cout<<accumulate(
        enemies.begin(),enemies.end(), 0ll,
        [imos](ll acc,const auto&e){
            return acc+std::max(0ll,e.hp-imos[e.y][e.x]);
        }
    )<<endl;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード