Submission #1239248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239248		faruk	Crossing (JOI21_crossing)	C++20	0 / 100	56 ms	5700 KiB

Main

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll P = 31;
const ll mod = 1e9 + 7;
const ll maxn = 3e5;
vector<ll> powp(maxn, 1), csum(maxn, 1);

ll merge(int l, int r, ll v1, ll v2) {
    return (powp[r - l + 1] * v2 + v1) % mod;
}

map<char, ll> trans = {{'J', 1}, {'O', 2}, {'I', 3}};
struct seggy { 
    int n;
    vector<ll> seg, lazy;
    seggy() {}
    seggy(int n) : n(n), seg(vector<ll>(4 * n)), lazy(vector<ll>(4 * n)) {}

    void push(int l, int r, int idx) {
        if (lazy[idx] == 0)
            return;
        seg[idx] = csum[r - l + 1] * lazy[idx] % mod;
        if (l != r)
            lazy[idx * 2] = lazy[idx * 2 + 1] = lazy[idx];
        lazy[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[idx] = val;
            push(l, r, idx);
            return;
        }
        if (l > R || r < L)
            return;
        int mid = (l + r) / 2;
        upd(l, mid, L, R, idx * 2, val);
        upd(mid + 1, r, L, R, idx * 2 + 1, val);
        seg[idx] = merge(l, mid, seg[idx * 2], seg[idx * 2 + 1]);
    }

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

    ll query() {
        push(0, n - 1, 1);
        if (0 != n - 1)
            seg[1] = merge(0, (n - 1) / 2, seg[1 * 2], seg[1 * 2 + 1]);
        return seg[1];
    }
};

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

    for (int i = 1; i < maxn; i++)
        powp[i] = powp[i - 1] * P % mod;
    csum[0] = 0;
    for (int i = 2; i < maxn; i++)
        csum[i] = (csum[i - 1] + powp[i - 1]) % mod;

    int n;
    cin >> n;
    vector<string> s(3);
    for (int i = 0; i < 3; i++)
        cin >> s[i];

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

    vector<int> cmp(n);
    iota(all(cmp), 0);
    vector<vector<int>> per(4); 
    /*
    0, 1  and 2 are diff
    1, 0 and 2 are diff
    2, 0 and 1 are diff
    3 all are diff
    */
    for (int i = 0; i < n; i++)
    {
        if (forced[i])
            continue;
        set<char> s1;
        for (int k = 0; k < 3; k++)
            s1.insert(s[k][i]);
        if (s1.size() == 3)
            per[3].push_back(i), cmp[i] = 3;
        else {
            for (int j = 0; j < 3; j++)
            {
                bool ok = true;
                for (int k = 0; k < 3; k++)
                    if (j != k and s[j][i] == s[k][i])
                        ok = false;
                if (ok)
                    per[j].push_back(i), cmp[i] = j;
            }
        }
    }

    int num_comps = 0;
    vector<vector<char>> variants(3, vector<char>(n));
    for (vector<int> ids : per)
    {
        if (!ids.empty())
            num_comps++;
        for (int i : ids)
        {
            variants[0][i] = s[0][i], variants[1][i] = s[1][i], variants[2][i] = s[2][i];
            for (int j = 0; j < 3; j++)
            {
                bool can_change = false;
                for (int k = 0; k < 3; k++)
                    if (j != k and variants[j][i] == variants[k][i])
                        can_change = true;
                if (!can_change)
                    continue;
                char me = 'J' + 'O' + 'I';
                for (int k = 0; k < 3; k++)
                    if (j != k)
                        me -= variants[k][i];
                variants[j][i] = me;
                break;
            }
        }
    }
    set<ll> poss;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                for (int l = 0; l < 3; l++) {
                    string I = "";
                    for (int t = 0; t < n; t++)
                    {
                        if (forced[t])
                            I += s[0][t];
                        else if (cmp[t] == 0)
                            I += variants[i][t];
                        else if (cmp[t] == 1)
                            I += variants[j][t];
                        else if (cmp[t] == 2)
                            I += variants[k][t];
                        else if (cmp[t] == 3)
                            I += variants[l][t];
                    }

                    ll hsh = 0;
                    for (int t = 0; t < n; t++)
                        hsh = (hsh + trans[I[t]] * powp[t]) % mod;
                    poss.insert(hsh);
                }
            }
        }
    }

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

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