Submission #1123342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123342		Whisper	Crossing (JOI21_crossing)	C++20	100 / 100	317 ms	26872 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX                     200005

int N, numQuery;
string s[3], now;
char other(char a, char b){
    if(a != 'J' and b != 'J') return 'J';
    if(a != 'O' and b != 'O') return 'O';
    if(a != 'I' and b != 'I') return 'I';
}


string cross(string &a, string &b){
    assert((int)a.size() == (int)b.size());
    int n = (int)a.size() - 1;
    string nw = "@";
    for (int i = 1; i <= n; ++i){
        if(a[i] == b[i]) nw += a[i];
        else nw += other(a[i], b[i]);
    }
    return nw;
}

namespace SUBTASK_3{
    bool check(void){
        return N <= 100;
    }

    queue<string> q;
    map<string, int> reach;
    void main(void){
        reach[s[0]] = reach[s[1]] = reach[s[2]] = true;
        q.emplace(s[0]);
        q.emplace(s[1]);
        q.emplace(s[2]);

        while(q.size()){
            string now = q.front(); q.pop();

            REP(i, 3){
                string nxt = cross(now, s[i]);
                if(!reach.count(nxt)){
                    q.emplace(nxt);
                    reach[nxt] = true;
                }
            }
        }
        cin >> numQuery >> now;
        now = '@' + now;
        if(reach.count(now)) cout << "Yes\n";
        else cout << "No\n";

        for (int qu = 1; qu <= numQuery; ++qu){
            int l, r; char c; cin >> l >> r >> c;

            FOR(i, l, r) now[i] = c;
            if(reach.count(now)) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

namespace SUBTASK_4{
    queue<string> q;
    map<string, int> reach;

    int conv(char c){
        if(c == 'J') return 1;
        if(c == 'O') return 2;
        if(c == 'I') return 3;
        assert(false);
    }

    const int base = 37;
    int hashID[MAX], Pw[MAX], sumPw[MAX];

    void prepare(void){
        reach[s[0]] = reach[s[1]] = reach[s[2]] = true;
        q.emplace(s[0]);
        q.emplace(s[1]);
        q.emplace(s[2]);

        while(q.size()){
            string now = q.front(); q.pop();

            REP(i, 3){
                string nxt = cross(now, s[i]);
                if(!reach.count(nxt)){
                    q.emplace(nxt);
                    reach[nxt] = true;
                }
            }
        }
        assert((int)reach.size() <= 12);
        int cnt = 0;
        for (auto&x : reach){
            ++cnt;
            for (int i = 1; i <= N; ++i){
                hashID[cnt] = (hashID[cnt] * base % Mod + (conv(x.first[i]))) % Mod;
            }
        }
        Pw[0] = 1;
        sumPw[0] = 1;
        for (int i = 1; i <= N; ++i){
            Pw[i] = Pw[i - 1] * base % Mod;
            sumPw[i] = (sumPw[i - 1] + Pw[i]) % Mod;
        }
    }

    struct Node{
        int len, hashID;
        Node(): len(0), hashID(0){}
        Node(int _len, int _hashID){
            len = _len, hashID = _hashID;
        }

        friend Node operator + (const Node&a, const Node& b){
            Node res;
            res.len = a.len + b.len;
            res.hashID = (a.hashID * Pw[b.len] % Mod + b.hashID % Mod) % Mod;
            return res;
        }
    };

    struct SegmentTree{
        int n;
        vector<Node> st;
        vector<int> lz;
        SegmentTree(int _n = 0){
            this -> n = _n;
            st.resize((n << 2) + 5);
            lz.resize((n << 2) + 5);
        }

        void pushDown(int nd, int l, int r){
            if(!lz[nd]) return;

            int m = (l + r) >> 1;
            st[nd << 1].hashID = lz[nd] * sumPw[m - l] % Mod;
            st[nd << 1 | 1].hashID = lz[nd] * sumPw[r - m - 1] % Mod;

            lz[nd << 1] = lz[nd];
            lz[nd << 1 | 1] = lz[nd];

            lz[nd] = 0;
        }

        void upd(int nd, int l, int r, int u, int v, int value){
            if (u > r || v < l) return;
            if (u <= l and v >= r){
                st[nd].hashID = value * sumPw[r - l] % Mod % Mod;
                st[nd].len = (r - l + 1);

                lz[nd] = value;
                return;
            }
            int m = (l + r) >> 1;
            pushDown(nd, l, r);
            upd(nd << 1, l, m, u, v, value);
            upd(nd << 1 | 1, m + 1, r, u, v, value);

            st[nd] = st[nd << 1] + st[nd << 1 | 1];
        }

        Node ask(int nd, int l, int r, int u, int v){
            if (u > r || v < l) return Node();
            if (u <= l and v >= r) return st[nd];

            int m = (l + r) >> 1;
            pushDown(nd, l, r);
            Node ql = ask(nd << 1, l, m, u, v);
            Node qr = ask(nd << 1 | 1, m + 1, r, u, v);
            return (ql + qr);
        }
        int answer(void){
            return st[1].hashID;
        }
    };

    void main(void){
        prepare();

        cin >> numQuery >> now;
        now = '@' + now;
        SegmentTree myit(N);

        for (int i = 1; i <= N; ++i){
            myit.upd(1, 1, N, i, i, conv(now[i]));
        }
        int n = (int)reach.size();
        bool ok = 0;
        for (int i = 1; i <= n; ++i){
            if(myit.answer() == hashID[i]) ok = 1;
        }

        cout << (ok ? "Yes\n" : "No\n");
        for (int qu = 1; qu <= numQuery; ++qu){
            int l, r; char c; cin >> l >> r >> c;
            int value = conv(c);

            myit.upd(1, 1, N, l, r, value);
            bool ok = 0;
            for (int i = 1; i <= n; ++i){
                if(myit.answer() == hashID[i]) ok = 1;
            }
            cout << (ok ? "Yes\n" : "No\n");
        }
    }
}
void process(void){
    cin >> N;
    REP(i, 3) {
        cin >> s[i];
        s[i] = '@' + s[i];
    }

    if(SUBTASK_3 :: check()){
        SUBTASK_3 :: main();
        return;
    }
    SUBTASK_4 :: main();
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Compilation message (stderr)

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

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