Submission #862220

#	Time	Username	Problem	Language	Result	Execution time	Memory
862220		lrvideckis	Round words (IZhO13_rowords)	C++17	100 / 100	150 ms	64912 KiB

rowords

#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 / 100