Submission #420198

#	Time	Username	Problem	Language	Result	Execution time	Memory
420198		Mamedov	Crossing (JOI21_crossing)	C++17	100 / 100	991 ms	11712 KiB

Main

#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define ui unsigned int
#define ull unsigned long long
#define f first
#define s second
#define oo 1000000000

using namespace std;


const int mod = 987657683;
const int up = 2e5 + 5;

int tree[up << 2], lazy[up << 2], pref[up];
string T;

map<char, int> num = {
    {'J', 0},
    {'O', 1},
    {'I', 2}
};

void pre_clc() {
    pref[0] = 0;
    pref[1] = 1;
    for(int i = 2; i < up; ++i) {
        pref[i] = (3ll * pref[i - 1]) % mod;
    }
    for(int i = 2; i < up; ++i) {
        pref[i] += pref[i - 1];
        if(pref[i] >= mod) pref[i] -= mod;
    }
}

int rangeHash(int l, int r) {
    return (pref[r] - pref[l - 1] + mod) % mod;
}

void build(int node, int l, int r) {
    if(l == r) {
        tree[node] = (num[T[l - 1]] * rangeHash(l, r)) % mod;
    }else {
        int mid = (l + r) >> 1;
        build(node << 1, l, mid);
        build((node << 1) | 1, mid + 1, r);
        tree[node] = (tree[node << 1] + tree[(node << 1) | 1]) % mod;
    }
}

void relax(int node, int l, int r) {
    if(l != r) {
        lazy[node << 1] = lazy[(node << 1) | 1] = lazy[node];
    }
    tree[node] = (lazy[node] * rangeHash(l, r)) % mod;
    lazy[node] = -1;
}

void update(int node, int l, int r, int ul, int ur, int val) {
    if(lazy[node] != -1) relax(node, l, r);
    if(l > ur || ul > r) return;
    if(ul <= l && r <= ur) {
        lazy[node] = val;
        relax(node, l, r);
    }else {
        int mid = (l + r) >> 1;
        update(node << 1, l, mid, ul, ur, val);
        update((node << 1) | 1, mid + 1, r, ul, ur, val);
        tree[node] = (tree[node << 1] + tree[(node << 1) | 1]) % mod;
    }
}

string Merge(string &s1, string &s2) {
    int n = (int)s1.size();
    string res;
    for(int i = 0; i < n; ++i) {
        if(s1[i] == s2[i]) {
            res += s1[i];
        }else {
            res += ('J' + 'O' + 'I' - s1[i] - s2[i]);
        }
    }
    return res;
}

int Hash(string s) {
    int n = (int)s.size();
    int res = 0;
    for(int i = 1; i <= n; ++i) {
        res += (num[s[i - 1]] * rangeHash(i, i)) % mod;
        if(res >= mod) res -= mod;
    }
    return res;
}
void solve() {
    pre_clc();
    int n;
    string s[3];
    cin >> n;
    cin >> s[0] >> s[1] >> s[2];
    set<string>st, tmp;
    tmp.insert(s[0]);
    tmp.insert(s[1]);
    tmp.insert(s[2]);

    bool has_new = true;
    while(has_new) {
        has_new = false;
        for(string s1 : tmp) {
            for(string s2 : tmp) {
                st.insert(Merge(s1, s2));
            }
        }
        if(st.size() > tmp.size()) {
            has_new = true;
        }
        tmp = st;
    }
    set<int>hasHash;
    for(string any : st) {
        hasHash.insert(Hash(any));
    }
    int q, l, r;
    char ch;
    cin >> q;
    cin >> T;
    memset(lazy, -1, sizeof(lazy));
    build(1, 1, n);
    if(hasHash.find(tree[1]) != hasHash.end()) {
        cout << "Yes\n";
    }else {
        cout << "No\n";
    }
    for(int i = 0; i < q; ++i) {
        cin >> l >> r >> ch;
        update(1, 1, n, l, r, num[ch]);
        if(hasHash.find(tree[1]) != hasHash.end()) {
        cout << "Yes\n";
        }else {
            cout << "No\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

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