Submission #1264545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264545		tvgk	Crossing (JOI21_crossing)	C++20	100 / 100	228 ms	23740 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
const long mxN = 2e5 + 7, MOD = 1e9 + 9, base = 5;

int n;
ll tree[mxN * 4], pw[mxN], pre[mxN], lazy[mxN * 4];
string s[20], t;
char chr[3] = {'J', 'O', 'I'};
map<int, bool> mp;

int cs(char j)
{
    for (int i = 0; i <= 2; i++)
    {
        if (chr[i] == j)
            return i;
    }
}

string XOR(string u, string v)
{
    string res;
    for (int i = 0; i < n; i++)
        res += chr[2 * (cs(u[i]) + cs(v[i])) % 3];
    return res;
}

int hsh(string s)
{
    ll res = 0;
    for (char i : s)
        res = (res * base + cs(i) + 1) % MOD;
    return res;
}

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[j] = cs(t[l - 1]) + 1;
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = (tree[j * 2] * pw[r - mid] + tree[j * 2 + 1]) % MOD;
}

void Upd(int u, int v, int nw, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return;

    if (u <= l && r <= v)
    {
        tree[j] = pre[r - l] * nw % MOD;
        lazy[j] = nw;
        return;
    }

    int mid = (l + r) / 2;

    if (lazy[j])
    {
        tree[j * 2] = lazy[j] * pre[mid - l] % MOD;
        tree[j * 2 + 1] = lazy[j] * pre[r - mid - 1] % MOD;
        lazy[j * 2] = lazy[j * 2 + 1] = lazy[j];
        lazy[j] = 0;
    }

    Upd(u, v, nw, j * 2, l, mid);
    Upd(u, v, nw, j * 2 + 1, mid + 1, r);
    tree[j] = (tree[j * 2] * pw[r - mid] + tree[j * 2 + 1]) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    int num = 0;
    for (; num <= 2; num++)
        cin >> s[num];

    for (int i = 0; i <= 2; i++)
    {
        for (int j = i + 1; j <= 2; j++)
            s[num++] = XOR(s[i], s[j]);
        s[num++] = XOR(XOR(s[i], s[(i + 1) % 3]), s[(i + 2) % 3]);
    }

    for (int i = 0; i < num; i++)
        mp[hsh(s[i])] = 1;

    pw[0] = pre[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        pw[i] = pw[i - 1] * base % MOD;
        pre[i] = (pre[i - 1] + pw[i]) % MOD;
    }

    int q;
    cin >> q;
    cin >> t;
    Build();

    if (mp[hsh(t)])
        cout << "Yes\n";
    else
        cout << "No\n";

    for (int i = 1; i <= q; i++)
    {
        int u, v;
        char nw;

        cin >> u >> v >> nw;

        Upd(u, v, cs(nw) + 1);

        if (mp[tree[1]])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'int cs(char)':
Main.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
   23 | }
      | ^

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