結果

問題 No.2761 Substitute and Search
ユーザー rniyarniya
提出日時 2024-05-17 22:08:02
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,188 ms / 4,000 ms
コード長 5,823 bytes
コンパイル時間 2,976 ms
コンパイル使用メモリ 262,236 KB
実行使用メモリ 138,880 KB
最終ジャッジ日時 2024-05-17 22:08:23
合計ジャッジ時間 19,553 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1,307 ms
138,880 KB
testcase_05 AC 2,188 ms
138,752 KB
testcase_06 AC 704 ms
138,624 KB
testcase_07 AC 1,628 ms
138,880 KB
testcase_08 AC 703 ms
138,752 KB
testcase_09 AC 1,464 ms
138,752 KB
testcase_10 AC 674 ms
138,880 KB
testcase_11 AC 1,696 ms
138,752 KB
testcase_12 AC 1,241 ms
138,752 KB
testcase_13 AC 1,221 ms
138,880 KB
testcase_14 AC 1,116 ms
138,752 KB
testcase_15 AC 1,143 ms
138,752 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::ostream& hash_impl::operator<<(std::ostream&, const modint&)':
main.cpp:95:90: warning: no return statement in function returning non-void [-Wreturn-type]
   95 |     friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; }
      |                                                                                          ^

ソースコード

diff # 

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

template <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& e : v) {
        is >> e;
    }
    return is;
}

template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
    for (std::string_view sep = ""; const auto& e : v) {
        os << std::exchange(sep, " ") << e;
    }
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) {
    return y < x and (x = std::forward<U>(y), true);
}

template <class T, class U = T> bool chmax(T& x, U&& y) {
    return x < y and (x = std::forward<U>(y), true);
}

template <class T> void mkuni(std::vector<T>& v) {
    std::ranges::sort(v);
    auto result = std::ranges::unique(v);
    v.erase(result.begin(), result.end());
}

template <class T> int lwb(const std::vector<T>& v, const T& x) {
    return std::distance(v.begin(), std::ranges::lower_bound(v, x));
}

#include <atcoder/segtree>

namespace hash_impl {

static constexpr unsigned long long mod = (1ULL << 61) - 1;

struct modint {
    modint() : _v(0) {}
    modint(unsigned long long v) {
        v = (v >> 61) + (v & mod);
        if (v >= mod) v -= mod;
        _v = v;
    }

    unsigned long long val() const { return _v; }

    modint& operator+=(const modint& rhs) {
        _v += rhs._v;
        if (_v >= mod) _v -= mod;
        return *this;
    }
    modint& operator-=(const modint& rhs) {
        if (_v < rhs._v) _v += mod;
        _v -= rhs._v;
        return *this;
    }
    modint& operator*=(const modint& rhs) {
        __uint128_t t = __uint128_t(_v) * rhs._v;
        t = (t >> 61) + (t & mod);
        if (t >= mod) t -= mod;
        _v = t;
        return *this;
    }
    modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); }

    modint operator-() const { return modint() - *this; }

    modint pow(long long n) const {
        assert(0 <= n);
        modint x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    modint inv() const { return pow(mod - 2); }

    friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; }
    friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; }
    friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; }
    friend modint operator/(const modint& lhs, const modint& rhs) { return modint(lhs) /= rhs; }
    friend bool operator==(const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; }
    friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; }

  private:
    unsigned long long _v;
};

uint64_t generate_base() {
    std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
    std::uniform_int_distribution<uint64_t> rand(2, mod - 1);
    return rand(mt);
}

modint base(generate_base());
std::vector<modint> power{1};

modint get_pow(int n) {
    if (n < int(power.size())) return power[n];
    int m = power.size();
    power.resize(n + 1);
    for (int i = m; i <= n; i++) power[i] = power[i - 1] * base;
    return power[n];
}

};  // namespace hash_impl

struct Hash {
    using mint = hash_impl::modint;
    mint x;
    int len;

    Hash() : x(0), len(0) {}
    Hash(mint x, int len) : x(x), len(len) {}

    Hash& operator+=(const Hash& rhs) {
        x = x * hash_impl::get_pow(rhs.len) + rhs.x;
        len += rhs.len;
        return *this;
    }
    Hash operator+(const Hash& rhs) { return *this += rhs; }
    bool operator==(const Hash& rhs) { return x == rhs.x and len == rhs.len; }
};

struct ReversibleHash {
    using mint = hash_impl::modint;
    mint x, rx;
    int len;

    ReversibleHash() : x(0), rx(0), len(0) {}
    ReversibleHash(mint x) : x(x), rx(x), len(1) {}
    ReversibleHash(mint x, mint rx, int len) : x(x), rx(rx), len(len) {}

    ReversibleHash rev() const { return ReversibleHash(rx, x, len); }

    ReversibleHash operator+=(const ReversibleHash& rhs) {
        x = x * hash_impl::get_pow(rhs.len) + rhs.x;
        rx = rx + rhs.rx * hash_impl::get_pow(len);
        len += rhs.len;
        return *this;
    }
    ReversibleHash operator+(const ReversibleHash& rhs) { return *this += rhs; }
    bool operator==(const ReversibleHash& rhs) { return x == rhs.x and rx == rhs.rx and len == rhs.len; }
};

using ll = long long;

using namespace std;

Hash op(Hash l, Hash r) { return l + r; }

Hash e() { return Hash(); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N, L, Q;
    cin >> N >> L >> Q;
    vector<string> S(N);
    cin >> S;

    vector<atcoder::segtree<Hash, op, e>> seg(N, atcoder::segtree<Hash, op, e>(L));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < L; j++) {
            seg[i].set(j, Hash(S[i][j], 1));
        }
    }
    for (; Q--;) {
        int type;
        cin >> type;
        if (type == 1) {
            int k;
            char c, d;
            cin >> k >> c >> d;
            k--;
            for (int i = 0; i < N; i++) {
                if (S[i][k] == c) {
                    S[i][k] = d;
                    seg[i].set(k, Hash(S[i][k], 1));
                }
            }
        } else {
            string t;
            cin >> t;
            int n = t.size();
            Hash sum = Hash();
            for (int i = 0; i < n; i++) sum += Hash(t[i], 1);
            int ans = 0;
            for (int i = 0; i < N; i++) ans += (seg[i].prod(0, n) == sum);
            cout << ans << '\n';
        }
    }
    return 0;
}
0