Submission #1255437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255437		chikien2009	Crossing (JOI21_crossing)	C++20	0 / 100	50 ms	13380 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const long long base = 7, mod = 1e9 + 7;
long long p[200001], pre[200001];

struct SEGMENT_TREE
{
    long long tree[800000];
    int val[800000];
    inline SEGMENT_TREE()
    {
        fill_n(tree, 8e5, 0);
        fill_n(val, 8e5, -1);
    }
    inline void UpdateNode(int ind, int l, int r)
    {
        if (val[ind] != -1)
        {
            tree[ind] = ((pre[r] - pre[l - 1] + mod) * val[ind]) % mod;
            if (l < r)
            {
                val[ind << 1] = val[ind << 1 | 1] = val[ind];
            }
            val[ind] = -1;
        }
    }
    inline void Update(int ind, int l, int r, int x, int y, int v)
    {
        UpdateNode(ind, l, r);
        if (r < x || y < l)
        {
            return;
        }
        if (x <= l && r <= y)
        {
            val[ind] = v;
            UpdateNode(ind, l, r);
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, y, v);
        Update(ind << 1 | 1, m + 1, r, x, y, v);
        tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
    }
} st;

int n, q, b, c;
char d;
string s;
vector<int> a[3];
set<int> se;

inline long long Convert(vector<int> v)
{
    long long ret = 0;
    for (int i = 1; i < v.size(); ++i)
    {
        (ret += p[i] * v[i]) %= mod;
    }
    return ret;
}

inline vector<int> Cross(vector<int> ina, vector<int> inb)
{
    vector<int> ret;
    for (int i = 0; i < ina.size(); ++i)
    {
        if (ina[i] == inb[i])
        {
            ret.push_back(ina[i]);
        }
        else
        {
            for (int j = 1; j <= 3; ++j)
            {
                if (ina[i] != j && inb[i] != j)
                {
                    ret.push_back(j);
                }
            }
        }
    }
    return ret;
}

int main()
{
    setup();

    p[1] = pre[1] = 1;
    for (int i = 2; i <= 2e5; ++i)
    {
        p[i] = (p[i - 1] * base) % mod;
        pre[i] = (pre[i - 1] + p[i]) % mod;
    }
    cin >> n;
    for (int i = 0; i < 3; ++i)
    {
        cin >> s;
        a[i] = {0};
        for (auto &j : s)
        {
            a[i].push_back(j == 'I' ? 1 : (j == 'J' ? 2 : 3));
        }
    }
    se.insert(Convert(a[0]));
    se.insert(Convert(a[1]));
    se.insert(Convert(a[2]));
    se.insert(Convert(Cross(a[0], a[1])));
    se.insert(Convert(Cross(a[0], a[2])));
    se.insert(Convert(Cross(a[1], a[2])));
    se.insert(Convert(Cross(a[0], Cross(a[1], a[2]))));
    se.insert(Convert(Cross(a[1], Cross(a[0], a[2]))));
    se.insert(Convert(Cross(a[2], Cross(a[1], a[0]))));
    cin >> q >> s;
    for (int i = 0; i < s.size(); ++i)
    {
        st.Update(1, 1, n, i + 1, i + 1, (s[i] == 'I' ? 1 : (s[i] == 'J' ? 2 : 3)));
    }
    cout << (se.find(st.tree[1]) != se.end() ? "Yes" : "No") << "\n";
    while (q--)
    {
        cin >> b >> c >> d;
        st.Update(1, 1, n, b, c, (d == 'I' ? 1 : (d == 'J' ? 2 : 3)));
        cout << (se.find(st.tree[1]) != se.end() ? "Yes" : "No") << "\n";
    }
    return 0;
}

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