제출 #1226352

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226352		bangan	Crossing (JOI21_crossing)	C++20	100 / 100	275 ms	21772 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long

#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

#define FOR1(a) for (int _ = 1; _ <= (a); _++)
#define FOR2(i, a) for (int i = 1; i <= (a); i++)
#define FOR3(i, a, b) for (int i = (a); i <= (b); i++)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define sep ' '
#define endl '\n'
#define print(a) cerr << #a << " = " << a << endl;

#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
#define pii pair<int, int>

#define pb push_back
#define eb emplace_back
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin());

#define LC (2 * v)
#define RC (2 * v + 1)
#define mid ((l+r) / 2)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 4;
const int cmod = 1;
const int mod[] = {1'000'000'009, 1'000'000'009};
const int B = 45589;

int n;
string a, b, c;

#define Hash array<int, cmod>

Hash power[N];
Hash pre[N];
vector<Hash> posib;

char lz[4*N];
Hash seg[4*N];

string merge(string x, string y) {
    string ret;
    for (int i=0; i<n; i++) {
        if (x[i]==y[i]) ret.pb(x[i]);
        else ret.pb(char(x[i] ^ y[i] ^ 'I' ^ 'J' ^ 'O'));
    }
    return ret;
}

void gen() {
    vector<string> all{a, b, c};
    UNIQUE(all);
    while (true) {
        int old_sz = all.size();
        vector<string> res;
        for (int i=0; i < all.size(); i++) for (int j = i+1; j < all.size(); j++) {
            res.pb(merge(all[i], all[j]));
        }
        for (auto x : res) all.pb(x);
        UNIQUE(all);
        if (all.size() == old_sz) break;
    }
    for (string s : all) {
        Hash h;
        for (int i=0; i<cmod; i++) h[i] = 0;
        for (int i=0; i<n; i++) for (int j=0; j<cmod; j++) {
            h[j] += s[i] * power[i][j] % mod[j];
            h[j] %= mod[j];
        }
        // print(h[0]);
        posib.pb(h);
    }
}

void prep() {
    for (int i=0; i<cmod; i++) power[0][i] = 1;
    for (int i=1; i<N; i++) for (int j=0; j<cmod; j++) {
        power[i][j] = power[i-1][j] * B % mod[j];
    }
    for (int i=1; i<N; i++) for (int j=0; j<cmod; j++) {
        pre[i][j] = power[i-1][j] + pre[i-1][j];
        pre[i][j] %= mod[j];
    }
    // print(pre[0][0]);
    // print(pre[1][0]);
    // print(pre[2][0]);
}

void push(int v, int l, int r) {
    if (lz[v] == 'a') return;
    for (int i=0; i<cmod; i++) {
        seg[v][i] = pre[r-l][i] * lz[v] % mod[i];
    }
    if (LC < 4*n) lz[LC] = lz[v];
    if (RC < 4*n) lz[RC] = lz[v];
    lz[v] = 'a';
}

void pull(int v, int l, int r) {
    push(v, l, r);
    push(LC, l, mid);
    push(RC, mid, r);
    for (int i=0; i<cmod; i++) {
        seg[v][i] = seg[LC][i] + power[mid - l][i] * seg[RC][i] % mod[i];
        seg[v][i] %= mod[i];
    }
}

void Modify(int s, int e, char x, int v=1, int l=0, int r=n) {
    push(v, l, r);
    if (s<=l && r<=e) {
        lz[v] = x;
        push(v, l, r);
        return;
    }
    if (s<mid) Modify(s, e, x, LC, l, mid);
    if (mid<e) Modify(s, e, x, RC, mid, r);
    pull(v, l, r);
}

Hash Get() {
    push(1, 0, n);
    pull(1, 0, n);
    return seg[1];
}

void SOLVE() {
    cin >> n;
    cin >> a >> b >> c;
    prep();
    gen();

    for (int i=1; i < 4*N; i++) {
        lz[i] = 'a';
        for (int j=0; j<cmod; j++) seg[i][j] = 0;
    }

    int q; cin >> q;
    string t; cin >> t;
    for (int i=0; i<n; i++) Modify(i, i+1, t[i]);

    {
        Hash res = Get();
        bool ans = false;
        for (Hash it : posib) if (it == res) ans = true;
        cout << (ans ? "Yes\n" : "No\n");
    }

    while (q--) {
        int l, r; char x;
        cin >> l >> r >> x;
        Modify(l-1, r, x);
        Hash res = Get();
        bool ans = false;
        for (Hash it : posib) if (it == res) ans = true;
        cout << (ans ? "Yes\n" : "No\n");
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1*'J' + B*'O' + B*B*'I';
    t %= mod[0];
    // print(t);
    int T = 1;
    // cin >> T;
    FOR(T) SOLVE();
}   

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