Submission #744305

#	Time	Username	Problem	Language	Result	Execution time	Memory
744305		GrindMachine	Crossing (JOI21_crossing)	C++17	100 / 100	806 ms	27664 KiB

Main

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> ps = {5791, 8237, 3067, 6991, 3527};
vector<int> mods = {791139137, 433567597, 271149607, 561259969, 222708581};
ll pows[N][2], pow_sum[N][2];

void precalc() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    shuffle(all(ps), rng);
    shuffle(all(mods), rng);

    rep(j, 2) {
        pows[0][j] = pow_sum[0][j] = 1;
        rep1(i, N - 1) {
            pows[i][j] = pows[i - 1][j] * ps[j] % mods[j];
            pow_sum[i][j] = (pow_sum[i - 1][j] + pows[i][j]) % mods[j];
        }
    }
}

struct Hash {
    ll a[2];

    Hash() {
        memset(a, 0, sizeof a);
    }

    Hash(ll x, ll y) {
        a[0] = x, a[1] = y;
    }

    Hash operator+(char ch) {
        Hash b;
        ll x = ch - 'a' + 1;

        rep(j, 2) {
            b.a[j] = (a[j] * ps[j] + x) % mods[j];
        }

        return b;
    }

    Hash operator+(ll x) {
        Hash b;

        rep(j, 2) {
            b.a[j] = (a[j] * ps[j] + x) % mods[j];
        }

        return b;
    }

    Hash operator+(Hash h) {
        Hash b;
        rep(j, 2) {
            b.a[j] = (a[j] + h.a[j]) % mods[j];
        }

        return b;
    }

    Hash operator-(Hash h) {
        Hash b;
        rep(j, 2) {
            b.a[j] = (a[j] - h.a[j] + mods[j]) % mods[j];
        }

        return b;
    }

    Hash poww(ll k) {
        Hash b;
        rep(j, 2) {
            b.a[j] = a[j] * pows[k][j] % mods[j];
        }

        return b;
    }

    bool operator==(Hash h) {
        rep(j, 2) {
            if (a[j] != h.a[j]) {
                return false;
            }
        }

        return true;
    }

    bool operator<(const Hash &h) const {
        rep(j, 2) {
            if (a[j] != h.a[j]) {
                return a[j] < h.a[j];
            }
        }

        return false;
    }
};

void print(Hash hsh) {
    cout << "[ ";
    rep(j, 2) cout << hsh.a[j] << " ";
    cout << "]";
}

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        Hash hsh;
        ll cnt = 0;

        data() {
            cnt = 0;
        }
    };

    struct lazy {
        char ch;

        lazy() {
            ch = '?';
        }
    };

    data d_neutral = data();
    lazy l_neutral = lazy();

    void merge(data &curr, data &left, data &right) {
        curr.hsh = left.hsh.poww(right.cnt) + right.hsh;
        curr.cnt = left.cnt + right.cnt;
    }

    void create(int x, int lx, int rx, T ch) {
        ll v = 0;
        if (ch == 'J') v = 1;
        else if (ch == 'O') v = 2;
        else v = 3;

        tr[x].hsh = Hash(v, v);
        tr[x].cnt = 1;
    }

    void modify(int x, int lx, int rx, T v) {
        lz[x].ch = v;
    }

    void propagate(int x, int lx, int rx) {
        char ch = lz[x].ch;
        if (ch == '?') return;

        ll v = 0;
        if (ch == 'J') v = 1;
        else if (ch == 'O') v = 2;
        else v = 3;

        ll guys = tr[x].cnt;

        ll hsh1 = v * pow_sum[guys - 1][0] % mods[0];
        ll hsh2 = v * pow_sum[guys - 1][1] % mods[1];
        tr[x].hsh = Hash(hsh1, hsh2);

        if (rx - lx > 1) {
            lz[2 * x + 1].ch = ch;
            lz[2 * x + 2].ch = ch;
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree() {

    }

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(string &a, int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, a[lx]);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(a, n, 2 * x + 1, lx, mid);
        build(a, n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(string &a, int n) {
        build(a, n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }
};

string get(string s1, string s2) {
    string s3 = "";
    rep(i, sz(s1)) {
        if (s1[i] == s2[i]) {
            s3.pb(s1[i]);
        }
        else {
            string joi = "JOI";
            for (auto ch : joi) {
                if (s1[i] != ch and s2[i] != ch) {
                    s3.pb(ch);
                }
            }
        }
    }

    return s3;
}

set<string> st;
string s1, s2, s3;

void go(string s) {
    if (st.count(s)) return;
    st.insert(s);

    go(get(s, s1));
    go(get(s, s2));
    go(get(s, s3));
}

void solve(int test_case)
{
    precalc();

    ll n; cin >> n;
    cin >> s1 >> s2 >> s3;

    for (auto s : {s1, s2, s3}) {
        go(s);
    }

    assert(sz(st) <= 9);

    set<Hash> hashes;

    trav(s, st) {
        Hash h;
        trav(ch, s) {
            ll v = 0;
            if (ch == 'J') v = 1;
            else if (ch == 'O') v = 2;
            else v = 3;

            h = h + v;
        }

        hashes.insert(h);
    }

    ll q; cin >> q;
    string t; cin >> t;
    t = "$" + t;

    lazysegtree<char> st(n + 5);
    st.build(t, n + 1);

    {
        Hash hsh = st.query(1, n).hsh;
        if (hashes.count(hsh)) yes;
        else no;
    }

    while (q--) {
        ll l, r; cin >> l >> r;
        char ch; cin >> ch;
        st.rupd(l, r, ch);

        Hash hsh = st.query(1, n).hsh;
        if (hashes.count(hsh)) yes;
        else no;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::string get(std::string, std::string)':
Main.cpp:30:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 | #define rep(i, n) for(int i = 0; i < n; ++i)
      |                                    ^
Main.cpp:315:5: note: in expansion of macro 'rep'
  315 |     rep(i, sz(s1)) {
      |     ^~~

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