제출 #1239290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239290		faruk	Crossing (JOI21_crossing)	C++20	49 / 100	1802 ms	78008 KiB

Main

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef __uint128_t ll;
typedef pair<ll, ll> pii;

const ll P = 23;
const ll mod2 = 1e16 + 7;
const ll mod1 = 1e15 + 9;
const ll maxn = 3e5;

ll merge(ll l, ll r, ll v1, ll v2, ll mod, vector<ll> &powp) {
    return ((powp.at(r - l + 1) * v2) % mod + v1) % mod;
}

map<char, ll> trans = {{'J', 43}, {'O', 39}, {'I', 53}};
struct seggy {
    ll mod;
    ll n;
    vector<ll> seg, lazy, powp, csum;
    seggy() {}
    seggy(ll n, ll mod) : mod(mod), n(n), seg(vector<ll>(4 * n)), lazy(vector<ll>(4 * n)) {
        powp = csum = vector<ll>(maxn, 1);
        for (ll i = 1; i < maxn; i++)
            powp.at(i) = powp.at(i - 1) * P % mod;
        csum.at(0) = 0;
        for (ll i = 2; i < maxn; i++)
            csum.at(i) = (csum.at(i - 1) + powp.at(i - 1)) % mod;
    }

    void push(ll l, ll r, ll idx) {
        if (lazy.at(idx) == 0)
            return;
        seg.at(idx) = csum.at(r - l + 1) * lazy.at(idx) % mod;
        if (l != r)
            lazy.at(idx * 2) = lazy.at(idx * 2 + 1) = lazy.at(idx);
        lazy.at(idx) = 0;
    }

    void upd(ll l, ll r, ll L, ll R, ll idx, ll val) {
        push(l, r, idx);
        if (l >= L and r <= R) {
            lazy.at(idx) = val;
            push(l, r, idx);
            return;
        }
        if (l > R || r < L)
            return;
        ll mid = (l + r) / 2;
        upd(l, mid, L, R, idx * 2, val);
        upd(mid + 1, r, L, R, idx * 2 + 1, val);
        seg.at(idx) = merge(l, mid, seg.at(idx * 2), seg.at(idx * 2 + 1), mod, powp);
    }

    void upd(ll l, ll r, ll val) {
        upd(0, n - 1, l, r, 1, val);
    }

    ll query() {
        push(0, n - 1, 1);
        return seg.at(1);
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<string> s(3);
    for (ll i = 0; i < 3; i++)
        cin >> s.at(i);

    vector<bool> forced(n, true);
    for (ll i = 0; i < n; i++) {
        if (s.at(0).at(i) != s.at(1).at(i) || s.at(0).at(i) != s.at(2).at(i) || s.at(1).at(i) != s.at(2).at(i))
            forced.at(i) = false;
    }

    vector<ll> cmp(n);
    vector<vector<ll>> per(4);
    for (ll i = 0; i < n; i++) {
        if (forced.at(i))
            continue;
        set<char> s1;
        for (ll k = 0; k < 3; k++)
            s1.insert(s.at(k).at(i));
        if (s1.size() == 3)
            per.at(3).push_back(i), cmp.at(i) = 3;
        else {
            for (ll j = 0; j < 3; j++) {
                bool ok = true;
                for (ll k = 0; k < 3; k++)
                    if (j != k and s.at(j).at(i) == s.at(k).at(i))
                        ok = false;
                if (ok)
                    per.at(j).push_back(i), cmp.at(i) = j;
            }
        }
    }

    ll num_comps = 0;
    vector<vector<char>> variants(3, vector<char>(n));
    for (vector<ll> ids : per) {
        if (!ids.empty())
            num_comps++;
        for (ll i : ids) {
            variants.at(0).at(i) = s.at(0).at(i), variants.at(1).at(i) = s.at(1).at(i), variants.at(2).at(i) = s.at(2).at(i);
            for (ll j = 0; j < 3; j++) {
                bool can_change = false;
                for (ll k = 0; k < 3; k++)
                    if (j != k and variants.at(j).at(i) == variants.at(k).at(i))
                        can_change = true;
                if (!can_change)
                    continue;
                char me = 'J' + 'O' + 'I';
                for (ll k = 0; k < 3; k++)
                    if (j != k)
                        me -= variants.at(k).at(i);
                variants.at(j).at(i) = me;
                break;
            }
        }
    }

    seggy seg1(n, mod1), seg2(n, mod2);
    set<ll> poss1, poss2;
    for (ll i = 0; i < 3; i++) {
        for (ll j = 0; j < 3; j++) {
            for (ll k = 0; k < 3; k++) {
                for (ll l = 0; l < 3; l++) {
                    string I = "";
                    for (ll t = 0; t < n; t++) {
                        if (forced.at(t))
                            I += s.at(0).at(t);
                        else if (cmp.at(t) == 0)
                            I += variants.at(i).at(t);
                        else if (cmp.at(t) == 1)
                            I += variants.at(j).at(t);
                        else if (cmp.at(t) == 2)
                            I += variants.at(k).at(t);
                        else if (cmp.at(t) == 3)
                            I += variants.at(l).at(t);
                    }

                    ll hsh = 0;
                    for (ll t = 0; t < n; t++)
                        hsh = (hsh + (trans[I.at(t)] * seg1.powp.at(t) % mod1)) % mod1;
                    poss1.insert(hsh);

                    hsh = 0;
                    for (ll t = 0; t < n; t++)
                        hsh = (hsh + (trans[I.at(t)] * seg2.powp.at(t) % mod2)) % mod2;
                    poss2.insert(hsh);
                }
            }
        }
    }

    string t;
    int q;
    cin >> q;
    cin >> t;
    for (ll i = 0; i < n; i++) {
        seg1.upd(i, i, trans[t.at(i)]);
        seg2.upd(i, i, trans[t.at(i)]);
    }
    for (ll Q = 0; Q <= q; Q++) {
        if (Q > 0) {
            int l, r;
            cin >> l >> r;
            char c;
            cin >> c;
            seg1.upd(l - 1, r - 1, trans[c]);
            seg2.upd(l - 1, r - 1, trans[c]);
        }
        if (poss1.count(seg1.query()) and poss2.count(seg2.query()))
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

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