Submission #1051885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051885		Sacharlemagne	Crossing (JOI21_crossing)	C++17	0 / 100	37 ms	2548 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MOD = 1e9+7, BASE = 5, MXN = 2e5+5;
ll Pow[MXN];
ll getVal(char c) {
    if (c == 'J') return 1;
    if (c == 'O') return 2;
    return 3;
}
char cross(char a, char b) {
    if (a == b) return a;
    if (a != 'O' && b != 'O') return 'O';
    if (a != 'J' && b != 'J') return 'J';
    return 'I';
}
string merge(string a, string b) {
    string c(a.size(), ' ');
    for (int i = 0; i<a.size(); ++i) {
        c[i] = cross(a[i], b[i]);
    }
    return c;
}
vector<ll> starter;
struct Node {
    ll l,r, mid, hash, set,sz;
    Node *lp, *rp;
    void blaSet(ll val) {
        hash = val * Pow[sz-1];
        set = val;
    }
    void pull() {
        hash = lp->hash * Pow[lp->sz] + rp->hash;
        hash %= MOD;
    }
    void push() {
        if (set != -1) {
            lp->blaSet(set), rp->blaSet(set);
            set = -1;
        }
    }
    Node(int l, int r) : l(l), r(r), mid((l+r)/2), sz(r-l+1) {
        if (l != r) {
            lp = new Node(l, mid), rp = new Node(mid+1,r);
            pull();
        }
        else blaSet(starter[l]);
    }
    void update(int s, int e, ll val) {
        if (s > r || e < l) return;
        if (s <= l && e >= r) {
            blaSet(val);
            return;
        }
        if (s <= mid) lp->update(s,e,val);
        if (e > mid) rp->update(s,e,val);
        pull();
    }
};
void init() {
    Pow[0] = 1;
    for (int i = 1; i<MXN; ++i) {
        Pow[i] = (Pow[i-1] * BASE) % MOD;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,q; cin >> n;
    init();

    vector<string> start(3);
    set<string> s;
    for (string &S :start) {
        cin >> S;
        s.insert(S);
    }
    /*for (int i = 0; i<3; ++i) for (int j = i+1; j<3; ++j) s.insert(merge(start[i], start[j]));
    s.insert(merge(start[0], merge(start[2], start[1])));
    s.insert(merge(start[1], merge(start[2], start[0])));
    s.insert(merge(start[2], merge(start[1], start[0])));
    */
    ll tot = 0;
    for (int i = 0; i<n; ++i) tot = (tot*BASE + getVal(start[0][i])) % MOD;
    cin >> q;
    string seq; cin >> seq;
    cout << (s.count(seq) ? "Yes" : "No") << '\n';
    starter.resize(n);
    for (int i = 0; i<n; ++i) starter[i] = getVal(seq[i]);
    Node *seg = new Node(0, n-1);
    while (q--) {
        int l,r; char c;
        cin >> l >> r >> c;
        ll ne = getVal(c);
        seg->update(l-1,r-1,ne);
        cout << (seg->hash == tot ? "Yes" : "No") << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i<a.size(); ++i) {
      |                     ~^~~~~~~~~

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