Submission #1131922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131922		new	Crossing (JOI21_crossing)	C++20	100 / 100	3426 ms	125548 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define v(x) (x.begin(), x.end())
#define pii pair<int, int>
const int MOD = 1e9 + 7;
using namespace std;
struct T
{
    string a;
    vector<int> rr;
    int n, cc;
    set<pair<pii, char>> st;
    void init(string as, string b)
    {
        a = as;
        n = (int)a.size();
        cc = 0;
        for (int i = 0; i < n; i++)
        {
            st.insert({{i, i}, b[i]});
            cc += (b[i] != a[i]);
        }
        rr.resize(n);
        int i = 0;
        while (i < n)
        {
            int j = i;
            while (j < n && a[i] == a[j])
                j++;
            j--;
            while (i <= j)
                rr[i++] = j;
        }
    }
    bool val(int l, int r, char x)
    {
        return (rr[l] >= r && a[l] == x);
    }
    void upd(int l, int r, char x)
    {
        auto it = st.lower_bound({{l + 1, 0}, 0});
        it--;
        auto [p, y] = (*it);
        if (p.ff < l)
        {
            cc -= !val(p.ff, p.ss, y);
            st.erase(it);
            st.insert({{p.ff, l - 1}, y});
            st.insert({{l, p.ss}, y});
            cc += !val(p.ff, l - 1, y);
            cc += !val(l, p.ss, y);
        }
        it = st.upper_bound({{r + 1, 0}, 0});
        it--;
        p = (*it).ff;
        y = (*it).ss;
        if (r < p.ss)
        {
            cc -= !val(p.ff, p.ss, y);
            st.erase(it);

            st.insert({{p.ff, r}, y});
            st.insert({{r + 1, p.ss}, y});

            cc += !val(p.ff, r, y);
            cc += !val(r + 1, p.ss, y);
        }

        while (1)
        {
            it = st.lower_bound({{l, 0}, 0});
            if (it == st.end() || (*it).ff.ff > r)
                break;

            auto [p, y] = (*it);

            cc -= !val(p.ff, p.ss, y);
            st.erase(it);
        }

        st.insert({{l, r}, x});
        cc += !val(l, r, x);
    }
    bool get()
    {
        return !cc;
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string a, b, c;
    cin >> a >> b >> c;
    vector<char> MOI = {'J', 'O', 'I'};
    auto f = [&](string x, string y)
    {
        string t;
        for (int i = 0; i < n; i++)
        {
            if (x[i] == y[i])
            {
                t += x[i];
                continue;
            }
            for (char s : MOI)
            {
                if (s != x[i] && s != y[i])
                {
                    t += s;
                    break;
                }
            }
        }
        return t;
    };

    vector<string> all = {a, b, c, f(a, b), f(b, c), f(a, c), f(f(a, b), c), f(f(b, c), a), f(f(a, c), b)};
    int q;
    cin >> q;
    string t;
    cin >> t;
    T T[9];
    for (int i = 0; i < 9; i++)
        T[i].init(all[i], t);
    auto check = [&](string s)
    {
        for (int i = 0; i < 9; i++)
        {
            if (T[i].get())
            {
                cout << "Yes" << "\n";
                return;
            }
        }
        cout << "No" << "\n";
        return;
    };
    check(t);
    while (q--)
    {
        int l, r;
        char c;
        cin >> l >> r >> c;
        l--;
        r--;
        for (int i = 0; i < 9; i++)
            T[i].upd(l, r, c);
        check(t);
    }
    return 0;
}

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