Submission #648025

#	Time	Username	Problem	Language	Result	Execution time	Memory
648025		BackNoob	Crossing (JOI21_crossing)	C++14	100 / 100	404 ms	36224 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int mod[2] = {(int) 1e9 + 7, (int) 1e9 + 9};
int pw[mxN][2];
int f[10][mxN][10];

int getidx(char ch)
{
    if(ch == 'J') return 0;
    if(ch == 'O') return 1;
    if(ch == 'I') return 2;
}

string tt;

struct SegmentLazy{
    int n;
    vector<pair<int, int>> t;
    vector<char> lz;
    SegmentLazy(){}
    SegmentLazy(int _n)
    {
        n = _n;
        int offset = 1;
        while(offset < n) offset *= 2;
        t.resize(offset * 2, make_pair(0, 0));
        lz.resize(offset * 2, '*');
    }

    void push_down(int v, int tl, int tr)
    {
        if(lz[v] == '*') return;
        int tm = (tl + tr) / 2;
        t[v * 2].fi = 1LL * f[getidx(lz[v])][tm - tl + 1][0];
        t[v * 2].se = 1LL * f[getidx(lz[v])][tm - tl + 1][1];
        t[v * 2 + 1].fi = 1LL * f[getidx(lz[v])][tr - tm][0];
        t[v * 2 + 1].se = 1LL * f[getidx(lz[v])][tr - tm][1];
        lz[v * 2] = lz[v * 2 + 1] = lz[v];
        lz[v] = '*';
    }

    void build(int v, int tl, int tr)
    {
        if(tl == tr) {
            t[v].fi = f[getidx(tt[tl - 1])][tr - tl + 1][0];
            t[v].se = f[getidx(tt[tl - 1])][tr - tl + 1][1];
            lz[v] = '*';
        }
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm);
            build(v * 2 + 1, tm + 1, tr);
            t[v].fi = (1LL * t[v * 2].fi * pw[tr - tm][0] % mod[0] + t[v * 2 + 1].fi) % mod[0];
            t[v].se = (1LL * t[v * 2].se * pw[tr - tm][1] % mod[1] + t[v * 2 + 1].se) % mod[1];
        }
    }

    void update(int v, int tl, int tr, int l, int r, char val)
    {
        if(l > r) return;
        if(tl == l && tr == r) {
            t[v].fi = f[getidx(val)][r - l + 1][0];
            t[v].se = f[getidx(val)][r - l + 1][1];
            lz[v] = val;
        }
        else {
            int tm = (tl + tr) / 2;
            push_down(v, tl, tr);
            update(v * 2, tl, tm, l, min(r, tm), val);
            update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, val);
            t[v].fi = (1LL * t[v * 2].fi * pw[tr - tm][0] % mod[0] + t[v * 2 + 1].fi) % mod[0];
            t[v].se = (1LL * t[v * 2].se * pw[tr - tm][1] % mod[1] + t[v * 2 + 1].se) % mod[1];
        }
    }

    void update(int l, int r, char val)
    {
        update(1, 1, n, l, r, val);
    }
} seg;

int n;
int q;
string s1;
string s2;
string s3;
string t;

char spec[3] = {'J', 'O', 'I'};

pair<int, int> findhash(string a, string b = "", string c = "")
{
    string res = a;
    if(sz(res) == sz(b)) {
        for(int i = 0; i < sz(b); i++) {
            if(res[i] == b[i]) continue;
            res[i] = spec[0 ^ 1 ^ 2 ^ getidx(res[i]) ^ getidx(b[i])];
        }
    }

    if(sz(res) == sz(c)) {
        for(int i = 0; i < sz(c); i++) {
            if(res[i] == c[i]) continue;
            res[i] = spec[0 ^ 1 ^ 2 ^ getidx(res[i]) ^ getidx(c[i])];
        }
    }

    pair<int, int> ans = {0, 0};
    for(int i = 0; i < sz(res); i++) {
        ans.fi = (1LL * ans.fi * base + res[i]) % mod[0];
        ans.se = (1LL * ans.se * base + res[i]) % mod[1];
    }
    //cout << res << ' ';
    //cout << ans.fi << ' ' << ans.se << endl;
    return ans;
}

void solve()
{
    cin >> n >> s1 >> s2 >> s3;
    cin >> q;
    cin >> t;

    tt = t;

    pw[0][0] = pw[0][1] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 2; j++) {
            pw[i][j] = 1LL * pw[i - 1][j] * base % mod[j];
        }
    }


    for(int i = 0; i < 3; i++) {
        char it = spec[i];
        f[i][0][0] = f[i][0][1] = 0;
        for(int j = 1; j <= n; j++)
        for(int k = 0; k < 2; k++)
            f[i][j][k] = (1LL * f[i][j - 1][k] * base + it) % mod[k];
    }

    vector<pair<int, int>> val;
    val.pb(findhash(s1));
    val.pb(findhash(s2));
    val.pb(findhash(s3));
    val.pb(findhash(s1, s2));
    val.pb(findhash(s1, s3));
    val.pb(findhash(s2, s3));
    val.pb(findhash(s2, s3, s1));
    val.pb(findhash(s1, s2, s3));
    val.pb(findhash(s1, s3, s2));
    sort(all(val));


    seg = SegmentLazy(n);
    seg.build(1, 1, n);

    pair<int, int> tmp = seg.t[1];
    //cout << tmp.fi << ' ' << tmp.se << endl;
    if(binary_search(all(val), tmp) == true) cout << "Yes" << endl;
    else cout << "No" << endl;

    while(q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        seg.update(l, r, c);

        pair<int, int> tmp = seg.t[1];
        //cout << tmp.fi << ' ' << tmp.se << endl;
        if(binary_search(all(val), tmp) == true) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".inp" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);

    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int getidx(char)':
Main.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

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