oj.uz

답안 #862220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862220 2023-10-17T18:09:17 Z lrvideckis 원형 문자열 (IZhO13_rowords) C++17
100 / 100
 150 ms 64912 KB 
#include <bits/stdc++.h>
using namespace std;

#define ssize(x) (int)(x).size()

template <class T> struct BIT {
    vector<T> s;
    BIT() {}
    BIT(int n) : s(n) {}
    BIT(const vector<T>& a) : s(a) {
        for (int i = 0; i < ssize(a); i++) {
            int j = i | (i + 1);
            if (j < ssize(a)) s[j] += s[i];
        }
    }
    inline void update(int i, T d) {
        assert(0 <= i && i < ssize(s));
        for (; i < ssize(s); i |= i + 1) s[i] += d;
    }
    inline T sum(int ri) const {
        assert(0 <= ri && ri <= ssize(s));
        T ret = 0;
        for (; ri > 0; ri &= ri - 1) ret += s[ri - 1];
        return ret;
    }
    inline T sum(int le, int ri) const {
        assert(le <= ri);
        return sum(ri) - sum(le);
    }
};
template <class T> struct lcs_dp {
    T t;
    vector<int> dp;
    lcs_dp(const T& a_t) : t(a_t), dp(ssize(t)) {
        iota(begin(dp), end(dp), 0);
    }
    void push_onto_s(int c) {
        for (int i = 0, v = -1; i < ssize(t); i++)
            if (c == t[i] || dp[i] < v) swap(dp[i], v);
    }
};
template <class T> vector<int> lcs_queries(const T& s, const T& t, const vector<array<int, 3>>& queries) {
    auto n = ssize(s), m = ssize(t), q = ssize(queries);
    vector qs(n, vector(m, vector<array<int, 2>>()));
    for (int i = 0; i < q; i++) {
        auto [s_ri, t_le, t_ri] = queries[i];
        assert(0 <= s_ri && s_ri <= n);
        assert(0 <= t_le && t_le <= t_ri && t_ri <= m);
        if (s_ri == 0 || t_le == m) continue;
        qs[s_ri - 1][t_le].push_back({t_ri, i});
    }
    lcs_dp lcs(t);
    vector<int> res(q);
    for (int i = 0; i < n; i++) {
        lcs.push_onto_s(s[i]);
        vector<int> init(m), dp_inv(m, -1);
        for (int j = 0; j < m; j++) {
            if (lcs.dp[j] == -1) init[j] = 1;
            else dp_inv[lcs.dp[j]] = j;
        }
        BIT<int> bit(init);
        for (int t_le = 0; t_le < m; t_le++) {
            for (auto [t_ri, idx] : qs[i][t_le])
                res[idx] = bit.sum(t_le, t_ri);
            if (dp_inv[t_le] != -1) bit.update(dp_inv[t_le], 1);
        }
    }
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    //freopen("rowords.in", "r", stdin);
    //freopen("rowords.out", "w", stdout);

    string s, t;
    cin >> s >> t;

    int res = 0;

    for(int times = 0; times < 2; times++) {
        vector<array<int, 3>> queries;
        for(int le = 0; le < ssize(t); le++) {
            queries.push_back({ssize(s), le, le + ssize(t)});
        }
        vector<int> all_lcs = lcs_queries(s, t + t, queries);

        res = max(res, *max_element(begin(all_lcs), end(all_lcs)));

        reverse(begin(s), end(s));
    }

    cout << res << '\n';

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 456 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 7 ms 4952 KB Output is correct
7 Correct 82 ms 47452 KB Output is correct
8 Correct 116 ms 47448 KB Output is correct
9 Correct 118 ms 47528 KB Output is correct
10 Correct 109 ms 47528 KB Output is correct
11 Correct 117 ms 52192 KB Output is correct
12 Correct 94 ms 60980 KB Output is correct
13 Correct 150 ms 60952 KB Output is correct
14 Correct 127 ms 54488 KB Output is correct
15 Correct 146 ms 64912 KB Output is correct
16 Correct 132 ms 52460 KB Output is correct
17 Correct 83 ms 39248 KB Output is correct
18 Correct 135 ms 61876 KB Output is correct
19 Correct 104 ms 47408 KB Output is correct
20 Correct 137 ms 55624 KB Output is correct
21 Correct 22 ms 12512 KB Output is correct
22 Correct 43 ms 21596 KB Output is correct
23 Correct 61 ms 30044 KB Output is correct
24 Correct 64 ms 31636 KB Output is correct
25 Correct 92 ms 43088 KB Output is correct