Submission #985289

#	Time	Username	Problem	Language	Result	Execution time	Memory
985289		underwaterkillerwhale	Crossing (JOI21_crossing)	C++17	0 / 100	61 ms	5088 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 1e6 + 7;
const ll Mod = 1e9 + 9;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 31;

int n, Q;
string T;
ll pw[N], hs[30][N];

struct Segment_Tree {
    int Range;
    ll st[N << 2], lz[N << 2];

    void init (int n) {
        Range = n;
        rep (i, 1, n << 2) lz[i] = -1;
    }
    void build (int id, int l, int r) {
        if (l == r) {
            st[id] = T[l - 1] - 'A';
            return;
        }
        int mid = l + r >> 1;
        build (id << 1, l, mid);
        build (id << 1| 1, mid + 1, r);
        st[id] = (st[id << 1] * pw[r - mid] % Mod + st[id << 1 | 1]) % Mod;
    }
    void down (int id, int l, int r) {
        int mid = l + r >> 1;
        if (lz[id] != -1) {
            st[id << 1] = hs[lz[id]][mid - l + 1];
            st[id << 1 | 1] = hs[lz[id]][r - mid];
            lz[id << 1] = lz[id];
            lz[id << 1 | 1] = lz[id];
        }
        lz[id] = -1;
    }
    void update (int id, int l, int r, int u, int v, int C) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id] = hs[C - 'A'][r - l + 1];
            lz[id] = C - 'A';
            return;
        }
        int mid = l + r >> 1;
        down (id, l, r);
        update (id << 1, l, mid, u, v, C);
        update (id << 1 | 1, mid + 1, r, u, v, C);
        st[id] = (st[id << 1] * pw[r - mid] % Mod + st[id << 1 | 1]) % Mod;
    }
    void update (int u, int v, int C) {
        return update (1, 1, Range, u, v, C);
    }
}ST;

void initHS () {
    pw[0] = 1;
    rep (i, 1, n * 2) pw[i] = pw[i - 1] * BASE;
    vector<char> c = {'J', 'O', 'I'};
    iter (id, c)
    rep (i, 1, n)
        hs[id - 'A'][i] = (hs[id - 'A'][i - 1] * BASE % Mod + id - 'A') % Mod;
}

ll getHS (string S) {
    ll res = 0;
    rep (i, 1, n) res = (res * BASE % Mod + S[i - 1]  - 'A') % Mod;
    return res;
}

void solution () {
    cin >> n;
    string A, B, C;
    cin >> A >> B >> C;
    vector<char> c = {'J', 'O', 'I'};

    set<string> S = {A, B, C};
    auto Merge = [] (string A, string B) {
        static string res;
        res.resize(SZ(A));
        rep (i, 0, SZ(A) - 1)
            if (A[i] == B[i]) res[i] = A[i];
            else {
                static set<char> c;
                c = {'J', 'O', 'I'};
                c.erase(A[i]);
                c.erase(B[i]);
                res[i] = *c.begin();
            }
        return res;
    };
    int prevsz = SZ(S);
    while (1) {
        static set<string> newStr;
        newStr.clear();
        iter (&id1, S)
        iter( &id2, S) newStr.insert(Merge(id1, id2));
        iter (&id, newStr) S.insert(id);
        if (SZ(S) == prevsz) break;
        else prevsz = SZ(S);
    }
    set<ll> vecHS;
    initHS();
    iter (&id, S) vecHS.insert(getHS(id));
    cin >> Q;
    cin >> T;
    ST.init(n);
    ST.build(1, 1, n);
    if (vecHS.find(ST.st[1]) != vecHS.end()) cout <<"Yes\n";
    else cout <<"No\n";
    rep (i, 1, Q) {
        int L, R;
        char C;
        cin >> L >> R >> C;
        ST.update(L, R, C);
        if (vecHS.find(ST.st[1]) != vecHS.end()) cout <<"Yes\n";
        else cout <<"No\n";
    }
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

Compilation message (stderr)

Main.cpp: In member function 'void Segment_Tree::build(int, int, int)':
Main.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void Segment_Tree::down(int, int, int)':
Main.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
Main.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = l + r >> 1;
      |                   ~~^~~

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