Submission #704964

#	Time	Username	Problem	Language	Result	Execution time	Memory
704964		Cyanmond	Crossing (JOI21_crossing)	C++17	100 / 100	1276 ms	115980 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 mod1 = 1000000007;
constexpr i64 mod2 = 998244353;

using T = std::pair<i64, i64>;
T addm1(T a, T b) {
    return {(a.first + b.first) % mod1, (a.second + b.second) % mod1};
}
T em() {
    return {0, 0};
}
T mapm1(i64 a, T b) {
    if (a == -1) return b;
    b.first = a * b.second;
    b.first %= mod1;
    return b;
}
i64 compm1(i64 a, i64 b) {
    if (a == -1) return b;
    return a;
}
i64 id() {
    return -1;
}

struct LazySegTreem1 {
    int n, size, logn;
    std::vector<T> node;
    std::vector<i64> lazy;

    void update(int i) {
        node[i] = addm1(node[2 * i], node[2 * i + 1]);
    }

    void ang(int i, i64 f) {
        node[i] = mapm1(f, node[i]);
        if (i < size) {
            lazy[i] = compm1(f, lazy[i]);
        }
    }

    void push(int i) {
        ang(2 * i, lazy[i]);
        ang(2 * i + 1, lazy[i]);
        lazy[i] = id();
    }

    LazySegTreem1() {}

    LazySegTreem1(const std::vector<T> &vec) {
        n = (int)vec.size();
        logn = 0;
        while ((1 << logn) < n) ++logn;
        size = 1 << logn;
        node.assign(2 * size, em());
        lazy.assign(size, id());
        std::copy(vec.begin(), vec.end(), node.begin() + size);
        for (int i = size - 1; i >= 1; --i) {
            update(i);
        }
    }

    void apply(int l, int r, i64 f) {
        l += size, r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) ang(l++, f);
            if (r & 1) ang(--r, f);
            l /= 2, r /= 2;
        }
        l = l2, r = r2;
        for (int d = 1; d <= logn; ++d) {
            if (((l >> d) << d) != l) update(l >> d);
            if (((r >> d) << d) != r) update((r - 1) >> d);
        }
    }

    T fold(int l, int r) {
        l += size, r += size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) push(l >> d);
            if (((r >> d) << d) != r) push((r - 1) >> d);
        }
        T pL = em(), pR = em();
        while (l < r) {
            if (l & 1) pL = addm1(pL, node[l++]);
            if (r & 1) pR = addm1(node[--r], pR);
            l /= 2;
            r /= 2;
        }
        return addm1(pL, pR);
    }
};

std::string cross(const std::string &a, const std::string &b) {
    std::string c;
    c.reserve(a.size());
    for (int i = 0; i < (int)a.size(); ++i) {
        if (a[i] == b[i]) {
            c.push_back(a[i]);
        } else {
            char x = 'J' xor 'O' xor 'I';
            x ^= a[i];
            x ^= b[i];
            c.push_back(x);
        }
    }
    return c;
}

constexpr i64 iHs = 7;
std::uniform_int_distribution<int> dist(0, 1000000000);
std::mt19937 mt(100);
std::array<i64, 3> h4 = {{999996919, 999976379, 999939407}}; 

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    std::vector<i64> powsm1(N);
    powsm1[0] = 1;
    for (int i = 1; i < N; ++i) {
        powsm1[i] = (powsm1[i - 1] * iHs) % mod1;
    }

    std::string S1, S2, S3;
    std::cin >> S1 >> S2 >> S3;
    int Q;
    std::cin >> Q;
    std::string T0;
    std::cin >> T0;
    std::vector<int> L(Q), R(Q);
    std::vector<char> C(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> R[i] >> C[i];
        --L[i];
    }

    std::set<std::string> flowers;
    std::queue<std::string> ns;
    ns.push(S1);
    ns.push(S2);
    ns.push(S3);
    flowers.insert(S1);
    flowers.insert(S2);
    flowers.insert(S3);
    while (not ns.empty()) {
        const auto t = ns.front();
        ns.pop();
        auto nflowers = flowers;
        for (const auto &q : flowers) {
            const auto r = cross(t, q);
            if (nflowers.find(r) == nflowers.end()) {
                nflowers.insert(r);
                ns.push(r);
            }
        }
        flowers = nflowers;
    }

    const int M = (int)flowers.size();
    assert(M <= 20);
    std::vector<std::string> fs;
    for (const auto &e : flowers) {
        fs.push_back(e);
    }
    std::vector<LazySegTreem1> segm1s(M);
    for (int x = 0; x < M; ++x) {
        std::vector<T> initVecm1(N);
        for (int i = 0; i < N; ++i) {
            const auto v = (fs[x][i] == 'J' ? h4[0] : (fs[x][i] == 'O' ? h4[1] : h4[2]));
            initVecm1[i] = {(v * powsm1[i]) % mod1, powsm1[i]};
        }
        segm1s[x] = LazySegTreem1(initVecm1);
    }
    std::vector<T> initVecm1(N);
    for (int i = 0; i < N; ++i) {
        const auto v = (T0[i] == 'J' ? h4[0] : (T0[i] == 'O' ? h4[1] : h4[2]));
        initVecm1[i] = {(v * powsm1[i]) % mod1, powsm1[i]};
    }
    LazySegTreem1 iUsegm1(initVecm1);

    std::cout << (flowers.find(T0) != flowers.end() ? "Yes" : "No") << std::endl;
    for (int x = 0; x < Q; ++x) {
        iUsegm1.apply(L[x], R[x], (C[x] == 'J' ? h4[0] : (C[x] == 'O' ? h4[1] : h4[2])));
        bool answer = false;
        for (int i = 0; i < M; ++i) {
            bool b = iUsegm1.fold(0, N).first == segm1s[i].fold(0, N).first;
            if (b) answer = true;
        }
        std::cout << (answer ? "Yes" : "No") << std::endl;
    }
    /*
    std::vector<int> sameLimitL(M, N), sameLimitR(M, 0);
    std::vector<std::vector<std::pair<int, int>>> pressInfo(M);
    for (int x = 0; x < M; ++x) {
        const auto &f = fs[x];
        for (int i = 0; i < N; ++i) {
            if (f[i] != T0[i]) {
                sameLimitL[x] = i;
                break;
            }
        }
        for (int i = N - 1; i >= 0; --i) {
            if (f[i] != T0[i]) {
                sameLimitR[i] = i + 1;
                break;
            }
        }

        int lastI = 0;
        for (int i = 1; i < N; ++i) {
            if (fs[lastI] != fs[i]) {
                pressInfo[x].push_back({lastI, i - lastI});
                lastI = i;
            }
        }
        pressInfo[x].push_back({lastI, N - lastI});
    }

    std::cout << (flowers.find(T0) != flowers.end() ? "Yes" : "No") << std::endl;
    for (int i = 0; i < Q; ++i) {
        bool answer = false;
        for (int x = 0; x < M; ++x) {
            // judge
            if (sameLimitL[x] < L[i]) {
                continue;
            }
            if (sameLimitR[x] > R[i]) {
                continue;
            }
            auto itr = std::lower_bound(pressInfo[x].begin(), pressInfo[x].end(), std::make_pair(L[i], N + 1));
            --itr;
            if (itr->first + itr->second < R[i]) {
                continue;
            }
            if (fs[x][L[i]] != C[i]) {
                continue;
            }
            answer = true;
            break;
        }
        std::cout << (answer ? "Yes" : "No") << std::endl;
    }
    */
}

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51