Submission #938953

#	Time	Username	Problem	Language	Result	Execution time	Memory
938953		riariti	Modsum (NOI12_modsum)	C++17	0 / 25	6 ms	3796 KiB

modsum

#line 1 "MODSUM.cpp"
#include <bits/stdc++.h>

#line 2 "/Users/jeff/Documents/git_repos/competitive/cplib/environment/dbg.hpp"

#if defined(local)
#include <debug>
#else
#define dbg(...)
#endif
#line 4 "MODSUM.cpp"

#line 9 "MODSUM.cpp"

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n))
        x *= 2;
    return x;
}

#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x)))
        x++;
    return x;
}

} // namespace internal

} // namespace atcoder

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e, class F, auto mapping, auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as F(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "compostiion must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
          F (*composition)(F, F), F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++)
            d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--)
            push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++)
            update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--)
            push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r)
            return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l)
                push(l >> i);
            if (((r >> i) << i) != r)
                push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1)
                sml = op(sml, d[l++]);
            if (r & 1)
                smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--)
            push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++)
            update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r)
            return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l)
                push(l >> i);
            if (((r >> i) << i) != r)
                push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1)
                    all_apply(l++, f);
                if (r & 1)
                    all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l)
                update(l >> i);
            if (((r >> i) << i) != r)
                update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n)
            return _n;
        l += size;
        for (int i = log; i >= 1; i--)
            push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0)
                l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0)
            return 0;
        r += size;
        for (int i = log; i >= 1; i--)
            push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2))
                r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size)
            lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

} // namespace atcoder

using S = int;

S op(S a, S b) { return a + b; }
S e() { return 0; }

using F = int;

S mapping(F f, S x) { return f + x; }

F composition(F a, F b) { return a + b; }
F id() { return 0; }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#define int std::int64_t

    int n;
    std::cin >> n;
    std::vector<int> v(n), w(n);
    for (int i = 0; i < 2 * n; i++) {
        auto k = i / 2;
        std::cin >> (i % 2 ? w[k] : v[k]);
    }

    dbg(n);
    dbg(v);
    dbg(w);

    // a^4 + 2a^2 + 1
    // let t = a^2 => (t + 1)^2
    // (t * (t + 2)) % 5 + 1 also
    // (a^2 + 1)^2
    //
    // 2 3
    // 10 11 12
    // 17
    //
    // 2 10 17 = 29
    // 2 11 17 = 30
    // 2 12 17 = 31
    // 3 10 17 = 30
    // 3 11 17 = 31
    // 3 12 17 = 32

    std::map<int, int> sum;
    std::vector<int> pth;
    auto rec = [&](auto &&self, int i, int s) {
        if (i == n) {
            sum[s]++;
            dbg(pth, s);

            return;
        }

        for (int j = v[i]; j <= w[i]; j++) {
            pth.push_back(j);
            self(self, i + 1, s + j);
            pth.pop_back();
        }
    };
    // rec(rec, 0, 0);

    dbg(sum);

    /*
    4 1 5 2 3 4 6 1 5
    17: [n = 4]
    18: [v = {1,2,4,1}]
    19: [w = {5,3,6,5}]
    */
    // we are going to find the count of every sum basically
    // after which we can trivially use above formula to find out
    // the sum
    //
    // the length is the length of last block v[n - 1], w[n - 1]
    //
    // 1   = 1
    // 1 1 = 2
    // 1 1 = 2
    //   1 = 1
    // 1 1 1 1 1
    //   2 2 2 2 2
    //     2 2 2 2 1
    //       1 1 1 1 1
    // 1 3 5 6 6 5 3 1
    //
    // x5
    // 1
    // 2 1
    // 2 2 1
    // 1 2 2
    //   1 2
    // 1
    // 1 1 1
    // 1 1 1 1
    //   1 1 1
    //       1
    //
    // first step 4 to 6
    // 1 1 1 1 1
    //   1 1 1 1 1
    //     1 1 1 1 1
    // =
    // 1 2 3 3 3 2 1
    //
    // second step 2 to 3
    // 1 2 3 3 3 2 1
    //   1 2 3 3 3 2 1
    // =
    // 1 3 5 6 6 5 3 1
    //
    // second step 1 to 5
    // 1 3 5 6 6 5 3 1
    //   1 3 5 6 6 5 3 1
    //     1 3 5 6 6 5 3 1
    //       1 3 5 6 6 5 3 1
    //         1 3 5 6 6 5 3 1
    // 1 4 9 15 21 25 21 15 9 4 1
    //
    // ofc the sum starts from the sum of v and ends at sum of w (which is the
    // index of counter)
    //
    // 55: [sum =
    // {(8,1),(9,4),(10,9),(11,15),(12,21),(13,25),(14,25),(15,21),(16,15),(17,9),(18,4),(19,1)}]
    // this is correct
    //
    // at max 100 steps
    //
    // observe that the each value of the vector is controlling only some extra
    // steps i.e
    // in this case 5
    // second step 1 to 5
    // 1 3 5 6 6 5 3 1
    //   1 3 5 6 6 5 3 1
    //     1 3 5 6 6 5 3 1
    //       1 3 5 6 6 5 3 1
    //         1 3 5 6 6 5 3 1
    // 1 1 1 1 1
    //   3 3 3 3 3
    //     5 5 5 5 5
    // see the 1 idx 0 of the vector acts for len number of elements (0 to 4
    // idxs) similarly for 3 idx 1 acts for len number of ele (1 to 5 idxs)
    //
    // use lazy segtree n times O(1000 ...)  should be possible

    std::reverse(v.begin(), v.end());
    std::reverse(w.begin(), w.end());

    auto l = w[0] - v[0] + 1;
    std::vector<int> a(l, 1);
    dbg(a);

    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(101 *
                                                                     1001);
    for (int i = 1; i < n; i++) {
        l = w[i] - v[i] + 1;
        dbg(l);

        for (int j = 0; j < a.size(); j++) {
            auto k = j + l - 1;
            seg.apply(j, k + 1, a[j]);
        }

        a.resize(a.size() + l - 1);
        for (int j = 0; j < a.size() + l; j++) {
            a[j] = seg.get(j);
            seg.set(j, 0);
        }
    }
    dbg(a);

    auto vs = std::accumulate(v.begin(), v.end(), 0);
    auto ws = std::accumulate(w.begin(), w.end(), 0);

    dbg(vs, ws, ws - vs + 1);
    assert(a.size() == ws - vs + 1);

    std::vector<std::pair<int, int>> vc;
    for (int i = 0, v = vs; i < a.size(); i++, v++) {
        vc.push_back({v, a[i]});
    }
    dbg(vc);

    std::int64_t ans = 0;
    for (auto [v, c] : vc) {
        auto k = std::pow(v, 2);
        std::int64_t res = static_cast<std::int64_t>(k) * (k + 2);
        res %= 5;
        res++;

        dbg(res);

        ans += res * c;
    }

    std::cout << ans << "\n";

#undef int

    return 0;
}

Compilation message (stderr)

MODSUM.cpp: In function 'int main()':
MODSUM.cpp:439:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
MODSUM.cpp:445:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from MODSUM.cpp:1:
MODSUM.cpp:456:21: warning: comparison of integer expressions of different signedness: 'std::vector<long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
MODSUM.cpp:459:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
MODSUM.cpp:327:10: warning: variable 'rec' set but not used [-Wunused-but-set-variable]

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5