제출 #420339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
420339		egorlifar	Crossing (JOI21_crossing)	C++17	100 / 100	411 ms	14588 KiB

Main

/*
KAMUI!
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓██████████▓▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓▓█████▓▓▓▓▓▓▓▓▓
▓▓▓▓▓▓▓███▓▒▒░▒▒▒▒▒░░░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓█▓▒▒▒▓▓████████▓▒▒░▒▒▒▓██▓▓▓▓▓▓
▓▓▓▓██▒▓████████████████▓░▒▒▒▒▓██▓▓▓▓ 
▓▓▓██▓███████▓▒░░░░░░░▒███▒░░▒▒▒██▓▓▓ 
▓▓█████████▓░░░░░░░░░░░░░██▓▓██████▓▓ 
▓▓█▒▓███████████▓▓▒▒▒▓▓██████████▓█▓▓ 
▓██▒▒▒███████████████████████████▓▓█▓ 
▓█▓▒▒░░████████▒░░░░▓███████████▓░▒█▓ 
▓█▒▒▒░██░▒████░░░░░░█████░░████▓░░▒█▓ 
▓█▒▒▒▒██░░░██▓░░░░░░░███▒░░████▒▒▒▒█▓ 
▓█▓▒▒▒██▒░░░▓█▓░░░░░▓█▓░░░▓███▓▒▒░▓█▓ 
▓█▓▒▒▒███░░░░████████▓░░░░░████▒▒▒▓█▓ 
▓▓█▒▒░▓███░░░▒███████▒░░░▒███▓▒▒▒▒█▓▓ 
▓▓██▒▒░████▒░░███████░░░▓███▓░▒▒▒██▓▓ 
▓▓▓██▒▒▒█████▓░░██████▒▓███▓▒░▒▒██▓▓▓ 
▓▓▓▓██▓▒░▓██████████████▓▒░▒▒▒▓██▓▓▓▓ 
▓▓▓▓▓▓██▓░▒▓█████████▒░░▒▒▒▒▓██▓▓▓▓▓▓ 
▓▓▓▓▓▓▓███▓▒▒▓██████▓░▒▒▒▓▓███▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓███▓▓▓▓███▓▓▓████▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓███████████▓▓▓▓▓▓▓▓▓▓▓▓▓ 
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double; 
const string FILENAME = "input";
const int Mod = 998244353;
const int P = 424243;


int sum(int a, int b) {
    return (a + b >= Mod ? a + b - Mod: a + b);
}


int mul(int a, int b) {
    return ((ll)a * b) % Mod;
}


int powm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}


int inv(int a) {
    return powm(a, Mod - 2);
}
 

const int MAXN = 200228;


int n;
string s[3];
int q;
string t0;
int p[MAXN];


struct node
{
    char mod = 0;
    int hsh = 0;
    int len = 0;
};


node operator +(const node& a, const node& b) {
    node c;
    c.len = a.len + b.len;
    c.hsh = sum(mul(a.hsh, p[b.len]), b.hsh);
    return c;
}


int h[3][MAXN];


struct rmq
{
    vector<node> d;
    int ss = 1;
    void init(int n, string t0) {
        ss = 1;
        while (ss < n) {
            ss <<= 1;
        }
        d.resize(2 * ss);
        for (int i = 0; i < n; i++) {
            d[ss + i].len = 1;
            d[ss + i].hsh = t0[i];
        }
        for (int i = ss - 1; i >= 1; i--) {
            d[i] = d[i * 2] + d[i * 2 + 1];
        }
    }
    void push(int v) {
        if (d[v].mod != 0) {
            d[v].hsh = h[(d[v].mod == 'J' ? 0: (d[v].mod == 'O' ? 1: 2))][d[v].len];
            if (v < ss) {
                d[v * 2].mod = d[v].mod;
                d[v * 2 + 1].mod = d[v].mod;
            }
            d[v].mod = 0;
        }
    }
    void add(int v, int vl, int vr, int l, int r, char c) {
        if (vl > r || vr < l) {
            push(v);
            return;
        }
        if (l <= vl && vr <= r) {
            d[v].mod = c;
            push(v);
            return;
        } 
        push(v);
        add(v * 2, vl, (vl + vr) / 2, l, r, c);
        add(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, c);
        d[v] = d[v * 2] + d[v * 2 + 1];
    }
};


void solve() {
    cin >> n;
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = mul(p[i - 1], P);
    }
    char c[3] = {'J', 'O', 'I'};
    for (int t = 0; t < 3; t++) {
        for (int i = 1; i <= n; i++) {
            h[t][i] = sum(mul(h[t][i - 1], P), c[t]); 
        }
    }
    for (int i = 0; i < 3; i++) {
        cin >> s[i];
    }    
    cin >> q;
    cin >> t0;
    vector<string> goods;
    for (int mask = 1; mask <= 7; mask++) {
        vector<int> st;
        for (int i = 0; i < 3; i++) {
            if (mask & (1 << i)) {
                st.pb(i);
            }
        }
        do {
            string cur;
            for (auto i: st) {
                if (cur.empty()) {
                    cur = s[i];
                } else {
                    for (int j = 0; j < n; j++) {
                        if (cur[j] == s[i][j]) {
                            continue;
                        } 
                        cur[j] = cur[j] ^ s[i][j] ^ 'J' ^ 'O' ^ 'I';
                    }
                }
            }
            goods.pb(cur);
        } while (next_permutation(all(st)));
    }
    bool ok = false;
    for (auto x: goods) {
        if (x == t0) {
            ok = true;
        }
    }
    if (ok) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    rmq kek;
    kek.init(n, t0);
    vector<int> goodhs;
    for (auto x: goods) {
        int cur = 0;
        for (auto y: x) {
            cur = sum(mul(cur, P), y);
        }  
        goodhs.pb(cur);
    }
    for (int it = 0; it < q; it++) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        kek.add(1, 1, kek.ss, l, r, c);
        kek.push(1);
        bool ok = false;
        for (auto x: goodhs) {
            if (x == kek.d[1].hsh) {
                ok = true;
            }
        }
        if (ok) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }      
}


int main() {
    //12:15
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   // read(FILENAME);
    int t;
    t = 1;
  //  cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

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