Submission #1240005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240005		trantrungkein	Crossing (JOI21_crossing)	C++20	100 / 100	227 ms	34520 KiB

Main

#include <bits/stdc++.h>
#define int long long 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<pair<int,int>> >
using namespace std;

const int Mod = 1e9 + 7;
const int N = 2e5 + 5;
const int base = 31;

inline int add(int a, int b) {
    a += b;
    if (a >= Mod) a -= Mod;
    return a;
}

inline int sub(int a, int b) {
    a -= b;
    if (a < 0) a += Mod;
    return a;
}

inline int mul(int a, int b) {
    return a * 1LL * b % Mod;
}

int Pow[N], pre[N], n;
struct hes {
    vector<int> hash;
    void Hash(string &s, int n) {   
        hash.resize(n + 3);
        For(i,1,n) hash[i] = add(hash[i - 1], mul(Pow[i], s[i] - 'A' + 1));
    }
};

string cross(string a, string b) {
    string s(n + 1, 'J'); 
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) s[i] = a[i];
        else {
            bool J = 0, O = 0, I = 0;
            if (a[i] == 'J' || b[i] == 'J') J = 1;
            if (a[i] == 'O' || b[i] == 'O') O = 1;
            if (a[i] == 'I' || b[i] == 'I') I = 1;
            if (!J) s[i] = 'J';
            else if (!O) s[i] = 'O';
            else s[i] = 'I';
        } 
    }    
    return " " + s.substr(1); 
}

int st[4 * N], Char[4 * N], lazy[4 * N];

void Push(int id, int l, int r) {
    if (!lazy[id]) return;
    st[id] = mul(Char[id] - 'A' + 1, sub(pre[r], pre[l - 1]));
    if (l != r) {
        lazy[2 * id] = lazy[2 * id + 1] = 1;
        Char[2 * id] = Char[2 * id + 1] = Char[id];
    }
    lazy[id] = 0;
}

void update(int id, int l, int r, int tl, int tr, char c) {   
    Push(id, l, r);
    if (l > tr || r < tl) return;
    if (tl <= l && r <= tr) {
        lazy[id] = 1;
        Char[id] = c;
        Push(id, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(2 * id, l, mid, tl, tr, c);
    update(2 * id + 1, mid + 1, r, tl, tr, c);
    st[id] = add(st[2 * id], st[2 * id + 1]);
}

unordered_map<int, bool> mp;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    Pow[0] = 1;
    For(i, 1, n) {
        Pow[i] = mul(Pow[i - 1], base);
        pre[i] = add(pre[i - 1], Pow[i]);
    }

    string a, b, c;
    cin >> a >> b >> c;
    a = ' ' + a;
    b = ' ' + b;
    c = ' ' + c;

    set<string> TH;
    TH.insert(a);
    TH.insert(b);
    TH.insert(c);
    TH.insert(cross(a, b));
    TH.insert(cross(a, c));
    TH.insert(cross(b, c));
    TH.insert(cross(cross(a, b), c));
    TH.insert(cross(cross(a, c), b));
    TH.insert(cross(cross(b, c), a));

    int num = TH.size();
    vector<hes> check(num + 1);
    int id = 0;
    for (string S : TH) {
        check[++id].Hash(S, n);
        mp[check[id].hash[n]] = 1;
    }

    string First;
    int q;
    cin >> q;
    cin >> First;
    First = ' ' + First;
    For(i, 1, n) update(1, 1, n, i, i, First[i]);

    cout << (mp.count(st[1]) ? "Yes" : "No") << '\n';

    while (q--) {
        int l, r;
        char ci;
        cin >> l >> r >> ci;
        update(1, 1, n, l, r, ci);
        cout << (mp.count(st[1]) ? "Yes" : "No") << '\n';
    }
}

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