Submission #534197

#	Time	Username	Problem	Language	Result	Execution time	Memory
534197		Monarchuwu	Crossing (JOI21_crossing)	C++17	26 / 100	246 ms	14996 KiB

Main

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;

const int N = 2e5 + 8, base = 7, mod = 1e9 + 2277;
const ll mod2 = (ll)mod * mod;
int n;
string sa, sb, sc;

ll add(ll a, ll b) { a += b; if (a >= mod) a -= mod; return a; }
ll ha, hb, hc, pw[N], prf[N];
int ch[256];
void init_hsh() {
    pw[0] = prf[0] = 1;
    for (int i = 1; i <= n; ++i) {
        pw[i] = pw[i - 1] * base % mod;
        prf[i] = add(prf[i - 1], pw[i]);
    }

    ch['J'] = 1, ch['O'] = 2, ch['I'] = 3;
    for (int i = 0; i < n; ++i) {
        ha = (ha + ch[sa[i]] * pw[i]) % mod;
        hb = (hb + ch[sb[i]] * pw[i]) % mod;
        hc = (hc + ch[sc[i]] * pw[i]) % mod;
    }
}

int q;
string t;
ll seg[N << 2];
int laz[N << 2];
void build(int u, int l, int r) {
    if (l == r) {
        seg[u] = ch[t[l]] * pw[l] % mod;
        return;
    }
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    build(u1, l, m);
    build(u2, m + 1, r);
    seg[u] = add(seg[u1], seg[u2]);
}
void upd(int u, int l, int r, int a, int b, int x) {
    if (a <= l && r <= b) {
        seg[u] = x * (prf[r] - prf[l] + pw[l] + mod) % mod;
        laz[u] = x;
        return;
    }
    int m = (l + r) >> 1, u1 = u << 1, u2 = u1 | 1;
    if (laz[u]) {
        seg[u1] = laz[u] * (prf[m] - prf[l] + pw[l] + mod) % mod;
        seg[u2] = laz[u] * (prf[r] - prf[m] + mod) % mod;
        laz[u1] = laz[u2] = laz[u];
        laz[u] = 0;
    }
    if (a <= m) upd(u1, l, m, a, b, x);
    if (m < b) upd(u2, m + 1, r, a, b, x);
    seg[u] = add(seg[u1], seg[u2]);
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> sa >> sb >> sc;

    cin >> q >> t;
    init_hsh();
    build(1, 0, n - 1);
    cout << (ha == seg[1] ? "Yes\n" : "No\n");

    int l, r; char c; while (q--) {
        cin >> l >> r >> c;
        upd(1, 0, n - 1, l - 1, r - 1, ch[c]);
        cout << (ha == seg[1] ? "Yes\n" : "No\n");
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

Main.cpp: In function 'void init_hsh()':
Main.cpp:24:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         ha = (ha + ch[sa[i]] * pw[i]) % mod;
      |                            ^
Main.cpp:25:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   25 |         hb = (hb + ch[sb[i]] * pw[i]) % mod;
      |                            ^
Main.cpp:26:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         hc = (hc + ch[sc[i]] * pw[i]) % mod;
      |                            ^
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:36:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   36 |         seg[u] = ch[t[l]] * pw[l] % mod;
      |                         ^
Main.cpp: In function 'int main()':
Main.cpp:73:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   73 |         upd(1, 0, n - 1, l - 1, r - 1, ch[c]);
      |                                           ^

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