Submission #1035107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035107		CommandMaster	Crossing (JOI21_crossing)	C++17	100 / 100	209 ms	19600 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>

inline int ser(char c) {
    return c == 'J' ? 1 : c == 'O' ? 2 : 3;
}

string comb(string&a, string&b) {
    string ans = a;
    for (int i = 0; i < b.size(); i++) {
        if (ans[i] != b[i]) ans[i] ^= 76 ^ b[i]; // ('J' ^ 'O' ^ 'I')
    }
    return ans;
}

const ll maxN = 2e5+5;
const ll MOD = 1e9+7;
const ll P = 5;
const ll invP1 = 250000002;

ll powP[maxN];

ll get_hash(string s) {
    ll hash = 0;
    for (int i = 0; i < s.size(); i++) {
        hash += powP[i] * ser(s[i]);
        hash %= MOD;
    }
    return hash;
}

inline ll cohash(ll val, int sz) {
    return val * (powP[sz] - 1) * invP1 % MOD;
}

struct SEG {
    vll toset;
    vll hash;

    void make(ll n) {
        toset.resize(n*4);
        hash.resize(n*4);
    }

    void push(ll v, ll tl, ll tm, ll tr) {
        if (toset[v]) {
            toset[v*2] = toset[v];
            hash[v*2] = cohash(toset[v], tm-tl+1);
            toset[v*2+1] = toset[v];
            hash[v*2+1] = cohash(toset[v], tr-tm);
            toset[v] = 0;
        }
    }

    void pull(ll v, ll tl, ll tm, ll tr) {
        hash[v] = (hash[v*2] + powP[tm - tl + 1] * hash[v*2+1]) % MOD;
    }

    void set(ll v, ll tl, ll tr, ll l, ll r, ll val) {
        if (l > r) return;
        if (tl == l && tr == r) {
            toset[v] = val;
            hash[v] = cohash(val, tr-tl+1);
            return;
        }
        ll tm = (tl + tr) / 2;
        push(v, tl, tm, tr);
        set(v*2, tl, tm, l, min(r, tm), val);
        set(v*2+1, tm+1, tr, max(l, tm+1), r, val);
        pull(v, tl, tm, tr);
    }

    void get(ll v, ll tl, ll tr, ll ind) {
        if (tl == tr) {
            cout << ind << ": " << hash[v] << '\n';
            return;
        }
        ll tm = (tl + tr) / 2;
        push(v, tl, tm, tr);
        if (ind <= tm) get(v*2, tl, tm, ind);
        else get(v*2+1, tm+1, tr, ind);
    }
};

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll n;
    cin >> n;
    powP[0] = 1;
    for (int i = 1; i <= n; i++) powP[i] = powP[i-1] * P % MOD;
    unordered_set<ll> hashes;
    {
        string s1, s2, s3;
        cin >> s1 >> s2 >> s3;
        hashes.insert(get_hash(s1));
        hashes.insert(get_hash(s2));
        hashes.insert(get_hash(s3));
        string s12 = comb(s1, s2);
        string s13 = comb(s1, s3);
        string s23 = comb(s2, s3);
        hashes.insert(get_hash(s12));
        hashes.insert(get_hash(s23));
        hashes.insert(get_hash(s13));
        hashes.insert(get_hash(comb(s12, s3)));
        hashes.insert(get_hash(comb(s23, s1)));
        hashes.insert(get_hash(comb(s13, s2)));
    }
    // cout << "hash: " << h << endl;
    ll q;
    cin >> q;
    SEG seg;
    seg.make(n);
    for (ll i =0 ; i < n; i++) {
        char c;
        cin >> c;
        seg.set(1, 0, n-1, i, i, ser(c));
    }
    // for (int i = 0; i < n; i++) seg.get(1, 0, n-1, i);
    if (hashes.count(seg.hash[1])) cout << "Yes\n";
    else cout << "No\n";
    while (q--) {
        ll l, r;
        char c;
        cin >> l >> r >> c;
        l--, r--;
        seg.set(1, 0, n-1, l, r, ser(c));
        // for (int i = 0; i < n; i++) seg.get(1, 0, n-1, i);
        if (hashes.count(seg.hash[1])) cout << "Yes\n";
        else cout << "No\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::string comb(std::string&, std::string&)':
Main.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < b.size(); i++) {
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'long long int get_hash(std::string)':
Main.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~

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