Submission #541194

#	Time	Username	Problem	Language	Result	Execution time	Memory
541194		Jomnoi	Crossing (JOI21_crossing)	C++17	100 / 100	222 ms	14288 KiB

Main

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

const int N = 2e5 + 10;
const int P = 31;
const int MOD = 1e9 + 7;

string pat = "JOI";
long long bn[N], qs[N];

long long get_hash(string s) {
    long long H = 0;
    int n = s.length();
    for(int i = 0; i < n; i++) {
        H = (H * P + s[i]) % MOD;
    }
    return H;
}

string crossing(string s, string t) {
    string res = "";
    int n = s.length();
    for(int i = 0; i < n; i++) {
        if(s[i] == t[i]) {
            res += s[i];
            continue;
        }
        
        for(int j = 0; j < 3; j++) {
            if(s[i] != pat[j] and t[i] != pat[j]) {
                res += pat[j];
                break;
            }
        }
    }
    return res;
}

class SegmentTree {
private :
    long long tree[4 * N];
    char lazy[4 * N];
public :
    long long merge(long long L, long long R, int l, int r) {
        int mid = (l + r) / 2;

        long long res = (L * bn[r - mid + 1] + R) % MOD;
        return res;
    }

    void build(int idx, int l, int r) {
        lazy[idx] = '*';
        if(l == r) {
            char t0;
            cin >> t0;
            tree[idx] = t0;
            return;
        }

        int mid = (l + r) / 2;
        build(idx * 2, l, mid);
        build(idx * 2 + 1, mid + 1, r);
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1], l, r);
    }  

    void push(int idx, int l, int r) {
        if(lazy[idx] == '*') {
            return;
        }

        tree[idx] = (qs[r - l + 1] * lazy[idx]) % MOD;
        if(l != r) {
            lazy[idx * 2] = lazy[idx * 2 + 1] = lazy[idx];
        }
        lazy[idx] = '*';
    }

    void update(int idx, int l, int r, int ql, int qr, char c) {
        push(idx, l, r);
        if(r < ql or qr < l) {
            return;
        }
        if(ql <= l and r <= qr) {
            lazy[idx] = c;
            push(idx, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(idx * 2, l, mid, ql, qr, c);
        update(idx * 2 + 1, mid + 1, r, ql, qr, c);
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1], l, r);
    }

    long long get_ans() {
        return tree[1];
    }

    void print(int idx, int l, int r) {
        push(idx, l, r);
        cout << l << " - " << r << " : " << tree[idx] << '\n';
        if(l == r) {
            return;
        }

        int mid = (l + r) / 2;
        print(idx * 2, l, mid);
        print(idx * 2 + 1, mid + 1, r);
    }
}ST;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    bn[1] = 1;
    qs[1] = 1;
    for(int i = 2; i <= n; i++) {
        bn[i] = (bn[i - 1] * P) % MOD;
        qs[i] = (qs[i - 1] + bn[i]) % MOD;
    }

    string s[6];
    cin >> s[0] >> s[1] >> s[2];

    set <long long> Hash;
    for(int i = 0; i < 3; i++) {
        Hash.insert(get_hash(s[i]));

        if(DEBUG) {
            cout << s[i] << ' ' << get_hash(s[i]) << '\n';
        }
    }

    for(int i = 0; i < 3; i++) {
        for(int j = i + 1; j < 3; j++) {
            s[2 + i + j] = crossing(s[i], s[j]);

            if(DEBUG) {
                cout << s[2 + i + j] << ' ' << get_hash(s[2 + i + j]) << '\n';
            }
            Hash.insert(get_hash(s[2 + i + j]));
        }
    }
    for(int i = 3; i < 6; i++) {
        for(int j = i + 1; j < 6; j++) {
            if(DEBUG) {
                cout << crossing(s[i], s[j]) << ' ' << get_hash(crossing(s[i], s[j])) << '\n';
            }

            Hash.insert(get_hash(crossing(s[i], s[j])));
        }
    }

    int q;
    cin >> q;

    ST.build(1, 0, n - 1); // input string t0

    if(DEBUG) {
        ST.print(1, 0, n - 1);
        cout << ST.get_ans() << " : ";
    }

    if(Hash.count(ST.get_ans())) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }

    while(q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        ST.update(1, 0, n - 1, l - 1, r - 1, c);

        if(DEBUG) {
            ST.print(1, 0, n - 1);
            cout << ST.get_ans() << " : ";
        }

        if(Hash.count(ST.get_ans())) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }
    return 0;
}

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