Submission #608979

#	Time	Username	Problem	Language	Result	Execution time	Memory
608979		Duy_e	Crossing (JOI21_crossing)	C++14	100 / 100	512 ms	25528 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e5 + 5;
const long long MOD = 2e9 + 11;
const long long base = 311;

int n, q;
string t[4];
ll id[N], f[N], pw[N];
map <ll, bool> mp;

string cross(string a, string b) {
    ll sum = 'J' ^ 'O' ^ 'I';
    string ans = "";
    for (int i = 0; i < n; i ++)
        if (a[i] == b[i])
            ans += a[i];
        else 
            ans += sum ^ a[i] ^ b[i];
    
    return ans;
}

ll decode(string &s) {
    ll ans = 0;
    for (char ch: s) 
        ans = (ans * base + ch) % MOD;

    return ans;
} 

void genall() {
    set <string> S;
    S.insert(t[1]);
    S.insert(t[3]);
    S.insert(t[2]);

    while (true) {
        bool check = false;
        for (string u: S) {
            for (string v: S) {
                string tmp = cross(u, v);
                if (!S.count(tmp)) {
                    check = true;
                    S.insert(tmp);
                    break;
                }
            } 
            if (check) break;
        }
        if (check == false) break;
    }

    for (string u: S) 
        mp[decode(u)] = true;
}

ll st[4 * N], lazy[4 * N];

void build(int id, int l, int r) {
    if (l > r) return;
    if (l == r) {
        ll v = t[0][l - 1];
        st[id] = pw[l] * v % MOD;
        return;
    }

    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    st[id] = (st[id << 1] + st[id << 1 | 1]) % MOD;
}

void down(int id, int l, int r) {
    if (lazy[id] == 0) return;
    ll &t = lazy[id];
    int mid = l + r >> 1;
    int u = id << 1, v = id << 1 | 1;
    lazy[u] = lazy[v] = t;
    st[u] = (f[mid] - f[l - 1] + MOD) * t % MOD;
    st[v] = (f[r] - f[mid] + MOD) * t % MOD;
    t = 0;
}

void upd(int id, int l, int r, int lef, int rig, ll ch) {
    if (l > rig || r < lef) return;
    if (lef <= l && r <= rig) {
        st[id] = (f[r] - f[l - 1] + MOD) * ch % MOD;
        lazy[id] = ch;
        return;
    }

    down(id, l, r);
    int mid = l + r >> 1;
    upd(id << 1, l, mid, lef, rig, ch);
    upd(id << 1 | 1, mid + 1, r, lef, rig, ch);
    st[id] = (st[id << 1] + st[id << 1 | 1]) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        //freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif
    
    cin >> n;
    cin >> t[1] >> t[2] >> t[3];
    genall();

    cin >> q;
    cin >> t[0];

    pw[n] = 1;
    for (int i = n - 1; i >= 1; i --) pw[i] = pw[i + 1] * base % MOD;
    for (int i = 1; i <= n; i ++) f[i] = (f[i - 1] + pw[i]) % MOD;

    build(1, 1, n);

    int l, r; char ch;

    if (mp[st[1]]) cout << "Yes\n"; else cout << "No\n";

    while (q --) {
        cin >> l >> r >> ch;
        upd(1, 1, n, l, r, ch);
        if (mp[st[1]]) cout << "Yes\n"; else cout << "No\n";
    }

    return 0;
}    
/**  /\_/\
*   (= ._.)
*   / >🍵 \>🍮
**/

Compilation message (stderr)

Main.cpp:138:9: warning: "/*" within comment [-Wcomment]
  138 | /**  /\_/\
      |          
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:74:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void down(int, int, int)':
Main.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, long long int)':
Main.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = l + r >> 1;
      |               ~~^~~

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