Submission #534308

#	Time	Username	Problem	Language	Result	Execution time	Memory
534308		Monarchuwu	Crossing (JOI21_crossing)	C++17	100 / 100	342 ms	15804 KiB

Main

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

const int N = 2e5 + 8, base = 7;
const ll mod = 10'000'000'000'000'061;
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], mer[256][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;
    mer['J']['O'] = mer['O']['J'] = mer['I']['I'] = 'I';
    mer['J']['I'] = mer['I']['J'] = mer['O']['O'] = 'O';
    mer['I']['O'] = mer['O']['I'] = mer['J']['J'] = 'J';
    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;
    }
}
ll gethsh(string s) {
    ll hsh(0);
    for (int i = 0; i < n; ++i)
        hsh = (hsh + ch[s[i]] * pw[i]) % mod;
    return hsh;
}
string Merge(string a, string b) {
    string c;
    for (int i = 0; i < n; ++i)
        c.push_back(mer[a[i]][b[i]]);
    return c;
}
unordered_set<ll> S;
void build_S() {
    vector<string> q[2];
    q[0].push_back(sa); S.insert(ha);
    q[0].push_back(sb); S.insert(hb);
    q[0].push_back(sc); S.insert(hc);

    while (!q[0].empty()) {
        string str = q[0].back(); q[0].pop_back();
        for (string str1 : q[1]) {
            string str2 = Merge(str, str1);
            ll hsh = gethsh(str2);

            if (!S.count(hsh)) {
                q[0].push_back(str2); S.insert(hsh);
            }
        }
        q[1].push_back(str);
    }
}

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;
    init_hsh();
    build_S();

    cin >> q >> t;
    build(1, 0, n - 1);
    cout << (S.count(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 << (S.count(seg[1]) ? "Yes\n" : "No\n");
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

Main.cpp: In function 'void init_hsh()':
Main.cpp:29:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   29 |         ha = (ha + ch[sa[i]] * pw[i]) % mod;
      |                            ^
Main.cpp:30:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |         hb = (hb + ch[sb[i]] * pw[i]) % mod;
      |                            ^
Main.cpp:31:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   31 |         hc = (hc + ch[sc[i]] * pw[i]) % mod;
      |                            ^
Main.cpp: In function 'll gethsh(std::string)':
Main.cpp:37:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |         hsh = (hsh + ch[s[i]] * pw[i]) % mod;
      |                             ^
Main.cpp: In function 'std::string Merge(std::string, std::string)':
Main.cpp:43:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |         c.push_back(mer[a[i]][b[i]]);
      |                             ^
Main.cpp:43:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   43 |         c.push_back(mer[a[i]][b[i]]);
      |                                   ^
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:73:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   73 |         seg[u] = ch[t[l]] * pw[l] % mod;
      |                         ^
Main.cpp: In function 'int main()':
Main.cpp:111:43: warning: array subscript has type 'char' [-Wchar-subscripts]
  111 |         upd(1, 0, n - 1, l - 1, r - 1, ch[c]);
      |                                           ^

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