#1114580 (C++23) No.3244 Range Multiple of 8 Query

提出ソース
結果

問題	No.3244 Range Multiple of 8 Query
ユーザー	ruthen71
提出日時	2025-08-22 23:08:28
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	4,973 ms / 5,000 ms
コード長	19,637 bytes
コンパイル時間	2,767 ms
コンパイル使用メモリ	234,804 KB
実行使用メモリ	48,916 KB
最終ジャッジ日時	2025-08-22 23:09:54
合計ジャッジ時間	81,487 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 40
権限があれば一括ダウンロードができます
ソースコード

raw source code
// #include "rcpl/my_template.hpp"
// #include "rcpl/data_structure/segment_tree.hpp"
// #include "rcpl/algebra/monoid_s/monoid_sum.hpp"
// using namespace std;
// 
// void solve() {
//     // TODO: Implement
//     INT(N, Q);
//     STR(S);
//     using Seg = SegmentTree<MonoidSum<int>>;
//     vector<Seg> seg(10, Seg(N));
//     REP(i, N) seg[S[i] - '0'].chset(i, 1);
//     vector<string> p8;
//     REP(i, 1000) {
//         string s = to_string(i);
//         if (LEN(s) != 3) continue;
//         if (s[0] == '0' or s[1] == '0' or s[2] == '0') continue;
//         if (i % 8 == 0) {
//             p8.push_back(s);
//         }
//     }
//     show(LEN(p8));
//     REP(q, Q) {
//         INT(L, R);
//         L--;
//         show(L);
//         show(R);
//         if (R - L == 1) {
//             if (S[L] == '8') {
//                 print(0);
//             } else {
//                 print(-1);
//             }
//             continue;
//         }
//         if (R - L == 2) {
//             string s = S.substr(L, 2);
//             if (stoll(s) % 8 == 0) {
//                 print(0);
//             } else {
//                 swap(s[0], s[1]);
//                 if (stoll(s) % 8 == 0) {
//                     print(1);
//                 } else {
//                     print(-1);
//                 }
//             }
//             continue;
//         }
//         // R - L >= 3
//         int ans = INF<int>;
// 
//         vector<vector<int>> pre(10);
//         {
//             vector<int> cnt(10);
//             REP(i, 1, 10) {
//                 REP(t, 3) {
//                     auto g = [&](int sm) -> bool { return sm <= cnt[i]; };
//                     int ind = seg[i].min_left(R, g);
//                     ind--;
//                     // ind >= L
//                     pre[i].push_back(ind);
//                     cnt[i]++;
//                 }
//             }
//         }
// 
//         FORE(s, p8) {
//             int ok = 1;
//             vector<int> cnt(10);
//             vector<int> inds;
//             RREP(i, 3) {
//                 int d = s[i] - '0';
//                 if (pre[d][cnt[d]] < L) {
//                     ok = 0;
//                     break;
//                 }
//                 // ind >= L
//                 inds.push_back(R - L - 1 - (pre[d][cnt[d]] - L));
//                 cnt[d]++;
//             }
//             if (!ok) continue;
//             show(inds);
//             int cur = 0;
//             REP(i, 3) {
//                 cur += inds[i];
//                 REP(j, i + 1, 3) {
//                     if (inds[i] > inds[j]) {
//                         inds[j]++;
//                     }
//                 }
//                 REP(i, 3) inds[i]--;
//             }
//             chmin(ans, cur);
//         }
// 
//         if (ans == INF<int>) {
//             print(-1);
//         } else {
//             print(ans);
//         }
//     }
//     return;
// }
// 
// int main() {
//     int T = 1;
//     // INT(T);
//     REP(T) solve();
//     return 0;
// }
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <forward_list>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#ifdef RUTHEN_LOCAL
#include <rcpl/debug.hpp>
#else
#define show(x) true
#endif

// type definition
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using f32 = float;
using f64 = double;
using f128 = long double;
template <class T> using pque = std::priority_queue<T>;
template <class T> using pqueg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// overload
#define overload4(_1, _2, _3, _4, name, ...) name
#define overload3(_1, _2, _3, name, ...) name
#define overload2(_1, _2, name, ...) name
// for loop
#define REP1(a) for (long long _ = 0; _ < (a); _++)
#define REP2(i, a) for (long long i = 0; i < (a); i++)
#define REP3(i, a, b) for (long long i = (a); i < (b); i++)
#define REP4(i, a, b, c) for (long long i = (a); i < (b); i += (c))
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP1(a) for (long long _ = (a) - 1; _ >= 0; _--)
#define RREP2(i, a) for (long long i = (a) - 1; i >= 0; i--)
#define RREP3(i, a, b) for (long long i = (b) - 1; i >= (a); i--)
#define RREP(...) overload3(__VA_ARGS__, RREP3, RREP2, RREP1)(__VA_ARGS__)
#define FORE1(x, a) for (auto&& x : a)
#define FORE2(x, y, a) for (auto&& [x, y] : a)
#define FORE3(x, y, z, a) for (auto&& [x, y, z] : a)
#define FORE(...) overload4(__VA_ARGS__, FORE3, FORE2, FORE1)(__VA_ARGS__)
#define FORSUB(t, s) for (long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
// function
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(a) std::sort((a).begin(), (a).end())
#define RSORT(a) std::sort((a).rbegin(), (a).rend())
#define REV(a) std::reverse((a).begin(), (a).end())
#define UNIQUE(a)                      \
    std::sort((a).begin(), (a).end()); \
    (a).erase(std::unique((a).begin(), (a).end()), (a).end())
#define LEN(a) (int)((a).size())
#define MIN(a) *std::min_element((a).begin(), (a).end())
#define MAX(a) *std::max_element((a).begin(), (a).end())
#define SUM1(a) std::accumulate((a).begin(), (a).end(), 0LL)
#define SUM2(a, x) std::accumulate((a).begin(), (a).end(), (x))
#define SUM(...) overload2(__VA_ARGS__, SUM2, SUM1)(__VA_ARGS__)
#define LB(a, x) std::distance((a).begin(), std::lower_bound((a).begin(), (a).end(), (x)))
#define UB(a, x) std::distance((a).begin(), std::upper_bound((a).begin(), (a).end(), (x)))
template <class T, class U> inline bool chmin(T& a, const U& b) { return (a > T(b) ? a = b, 1 : 0); }
template <class T, class U> inline bool chmax(T& a, const U& b) { return (a < T(b) ? a = b, 1 : 0); }
template <class T, class S> inline T floor(const T x, const S y) {
    assert(y);
    return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1)));
}
template <class T, class S> inline T ceil(const T x, const S y) {
    assert(y);
    return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y));
}
template <class T, class S> std::pair<T, T> inline divmod(const T x, const S y) {
    T q = floor(x, y);
    return {q, x - q * y};
}
// 10 ^ n
constexpr long long TEN(int n) { return (n == 0) ? 1 : 10LL * TEN(n - 1); }
// 1 + 2 + ... + n
#define TRI1(n) ((n) * ((n) + 1LL) / 2)
// l + (l + 1) + ... + r
#define TRI2(l, r) (((l) + (r)) * ((r) - (l) + 1LL) / 2)
#define TRI(...) overload2(__VA_ARGS__, TRI2, TRI1)(__VA_ARGS__)
// bit operation
// bit[i] (= 0 or 1)
#define IBIT(bit, i) (((bit) >> (i)) & 1)
// (0, 1, 2, 3, 4) -> (0, 1, 3, 7, 15)
#define MASK(n) ((1LL << (n)) - 1)
#define POW2(n) (1LL << (n))
// (0, 1, 2, 3, 4) -> (0, 1, 1, 2, 1)
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(i64 x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(i64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(i64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
// binary search (integer)
template <class T, class F> T bin_search(T ok, T ng, F& f) {
    // assert(f(ok) and !f(ng));
    while ((ok > ng ? ok - ng : ng - ok) > 1) {
        T md = (ng + ok) >> 1;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}
// binary search (real number)
template <class T, class F> T bin_search_real(T ok, T ng, F& f, const int iter = 100) {
    // assert(f(ok) and !f(ng));
    for (int _ = 0; _ < iter; _++) {
        T md = (ng + ok) / 2;
        (f(md) ? ok : ng) = md;
    }
    return ok;
}
// floor(sqrt(x))
template <class T> constexpr T sqrt_floor(T x) { return T(sqrtl(x)); }
// check if [l1, r1) and [l2, r2) intersect
template <class T> constexpr bool intersect(const T l1, const T r1, const T l2, const T r2) { return std::max(l1, l2) < std::min(r1, r2); }
// check if [a.first, a.second) and [b.first, b.second) intersect
template <class T> constexpr bool intersect(const std::pair<T, T>& a, const std::pair<T, T>& b) { return intersect(a.first, a.second, b.first, b.second); }
// rotate matrix counterclockwise by pi / 2
template <class T> void rot(std::vector<std::vector<T>>& a) {
    if ((int)(a.size()) == 0) return;
    if ((int)(a[0].size()) == 0) return;
    int n = (int)(a.size()), m = (int)(a[0].size());
    std::vector res(m, std::vector<T>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            res[m - 1 - j][i] = a[i][j];
        }
    }
    a.swap(res);
}
// const value
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// infinity
template <class T> constexpr T INF = 0;
template <> constexpr int INF<int> = 1'000'000'000;                 // 1e9
template <> constexpr i64 INF<i64> = i64(INF<int>) * INF<int> * 2;  // 2e18
template <> constexpr u32 INF<u32> = INF<int>;                      // 1e9
template <> constexpr u64 INF<u64> = INF<i64>;                      // 2e18
template <> constexpr f32 INF<f32> = INF<i64>;                      // 2e18
template <> constexpr f64 INF<f64> = INF<i64>;                      // 2e18
template <> constexpr f128 INF<f128> = INF<i64>;                    // 2e18
// I/O
// input
template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto&& i : v) is >> i;
    return is;
}
template <class... T> void in(T&... a) { (std::cin >> ... >> a); }
void scan() {}
template <class Head, class... Tail> void scan(Head& head, Tail&... tail) {
    in(head);
    scan(tail...);
}
// input macro
#define INT(...)     \
    int __VA_ARGS__; \
    scan(__VA_ARGS__)
#define I64(...)     \
    i64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define U32(...)     \
    u32 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define U64(...)     \
    u64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F32(...)     \
    f32 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F64(...)     \
    f64 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define F128(...)     \
    f128 __VA_ARGS__; \
    scan(__VA_ARGS__)
#define STR(...)             \
    std::string __VA_ARGS__; \
    scan(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    scan(__VA_ARGS__)
#define VEC(type, name, size)     \
    std::vector<type> name(size); \
    scan(name)
#define VEC2(type, name1, name2, size)          \
    std::vector<type> name1(size), name2(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, size)                \
    std::vector<type> name1(size), name2(size), name3(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, size)                      \
    std::vector<type> name1(size), name2(size), name3(size), name4(size); \
    for (int i = 0; i < size; i++) scan(name1[i], name2[i], name3[i], name4[i])
#define VV(type, name, h, w)                       \
    std::vector name((h), std::vector<type>((w))); \
    scan(name)
// output
template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    auto n = v.size();
    for (size_t i = 0; i < n; i++) {
        if (i) os << ' ';
        os << v[i];
    }
    return os;
}
template <class... T> void out(const T&... a) { (std::cout << ... << a); }
void print() { out('\n'); }
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
    out(head);
    if (sizeof...(Tail)) out(' ');
    print(tail...);
}
// for interactive problems
void printi() { std::cout << std::endl; }
template <class Head, class... Tail> void printi(Head&& head, Tail&&... tail) {
    out(head);
    if (sizeof...(Tail)) out(' ');
    printi(tail...);
}
// bool output
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void NO(bool t = 1) { YES(!t); }
void No(bool t = 1) { Yes(!t); }
void no(bool t = 1) { yes(!t); }
void POSSIBLE(bool t = 1) { print(t ? "POSSIBLE" : "IMPOSSIBLE"); }
void Possible(bool t = 1) { print(t ? "Possible" : "Impossible"); }
void possible(bool t = 1) { print(t ? "possible" : "impossible"); }
void IMPOSSIBLE(bool t = 1) { POSSIBLE(!t); }
void Impossible(bool t = 1) { Possible(!t); }
void impossible(bool t = 1) { possible(!t); }
void FIRST(bool t = 1) { print(t ? "FIRST" : "SECOND"); }
void First(bool t = 1) { print(t ? "First" : "Second"); }
void first(bool t = 1) { print(t ? "first" : "second"); }
void SECOND(bool t = 1) { FIRST(!t); }
void Second(bool t = 1) { First(!t); }
void second(bool t = 1) { first(!t); }
// I/O speed up
struct SetUpIO {
    SetUpIO() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        std::cout << std::fixed << std::setprecision(20);
    }
} set_up_io;
template <class MS> struct SegmentTree {
   public:
    using S = typename MS::S;
    SegmentTree() : SegmentTree(0) {}
    SegmentTree(int n) : SegmentTree(std::vector<S>(n, MS::e())) {}
    SegmentTree(const std::vector<S>& v) : n((int)(v.size())) {
        log = 0;
        while ((1U << log) < (unsigned int)(n)) log++;
        size = 1 << log;
        d = std::vector<S>(size << 1, MS::e());
        for (int i = 0; i < n; i++) d[i + size] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

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

    void chset(int p, const S& x) {
        assert(0 <= p and p < n);
        p += size;
        d[p] = MS::op(d[p], x);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return d[p + size];
    }

    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        S sml = MS::e(), smr = MS::e();
        l += size;
        r += size;

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

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

    template <class G> int max_right(int l, G& g) const {
        assert(0 <= l and l <= n);
        assert(g(MS::e()));
        if (l == n) return n;
        l += size;
        S sm = MS::e();
        do {
            while ((l & 1) == 0) l >>= 1;
            if (!g(MS::op(sm, d[l]))) {
                while (l < size) {
                    l <<= 1;
                    if (g(MS::op(sm, d[l]))) {
                        sm = MS::op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = MS::op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class G> int min_left(int r, G& g) const {
        assert(0 <= r and r <= n);
        assert(g(MS::e()));
        if (r == 0) return 0;
        r += size;
        S sm = MS::e();
        do {
            r--;
            while (r > 1 and (r & 1)) r >>= 1;
            if (!g(MS::op(d[r], sm))) {
                while (r < size) {
                    r = (r << 1) | 1;
                    if (g(MS::op(d[r], sm))) {
                        sm = MS::op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = MS::op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    std::vector<S> make_vector() {
        std::vector<S> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i);
        return vec;
    }

   private:
    int n, log, size;
    std::vector<S> d;
    inline void update(int k) { d[k] = MS::op(d[k << 1], d[(k << 1) | 1]); }
};
// MS
template <class T> struct MonoidSum {
    using S = T;
    static constexpr S op(S a, S b) { return a + b; }
    static constexpr S e() { return T(0); }
};
using namespace std;

void solve() {
    // TODO: Implement
    INT(N, Q);
    STR(S);
    using Seg = SegmentTree<MonoidSum<int>>;
    vector<Seg> seg(10, Seg(N));
    REP(i, N) seg[S[i] - '0'].chset(i, 1);
    vector<string> p8;
    REP(i, 1000) {
        string s = to_string(i);
        if (LEN(s) != 3) continue;
        if (s[0] == '0' or s[1] == '0' or s[2] == '0') continue;
        if (i % 8 == 0) {
            p8.push_back(s);
        }
    }
    show(LEN(p8));
    REP(q, Q) {
        INT(L, R);
        L--;
        show(L);
        show(R);
        if (R - L == 1) {
            if (S[L] == '8') {
                print(0);
            } else {
                print(-1);
            }
            continue;
        }
        if (R - L == 2) {
            string s = S.substr(L, 2);
            if (stoll(s) % 8 == 0) {
                print(0);
            } else {
                swap(s[0], s[1]);
                if (stoll(s) % 8 == 0) {
                    print(1);
                } else {
                    print(-1);
                }
            }
            continue;
        }
        // R - L >= 3
        int ans = INF<int>;

        vector<vector<int>> pre(10);
        {
            vector<int> cnt(10);
            REP(i, 1, 10) {
                REP(t, 3) {
                    auto g = [&](int sm) -> bool { return sm <= cnt[i]; };
                    int ind = seg[i].min_left(R, g);
                    ind--;
                    // ind >= L
                    pre[i].push_back(ind);
                    cnt[i]++;
                }
            }
        }

        FORE(s, p8) {
            int ok = 1;
            vector<int> cnt(10);
            vector<int> inds;
            RREP(i, 3) {
                int d = s[i] - '0';
                if (pre[d][cnt[d]] < L) {
                    ok = 0;
                    break;
                }
                // ind >= L
                inds.push_back(R - L - 1 - (pre[d][cnt[d]] - L));
                cnt[d]++;
            }
            if (!ok) continue;
            show(inds);
            int cur = 0;
            REP(i, 3) {
                cur += inds[i];
                REP(j, i + 1, 3) {
                    if (inds[i] > inds[j]) {
                        inds[j]++;
                    }
                }
                REP(i, 3) inds[i]--;
            }
            chmin(ans, cur);
        }

        if (ans == INF<int>) {
            print(-1);
        } else {
            print(ans);
        }
    }
    return;
}

int main() {
    int T = 1;
    // INT(T);
    REP(T) solve();
    return 0;
}
yukicoder

結果

ソースコード
