Submission #750993

#	Time	Username	Problem	Language	Result	Execution time	Memory
750993		sysia	Crossing (JOI21_crossing)	C++17	100 / 100	480 ms	101008 KiB

Main

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void add(int &a, int b){
    a += b;
    if (a >= mod) a-=mod;
}

int add2(int a, int b){
    add(a, b);
    return a;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += mod;
}

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

T f(T a, T b){
    return T{add2(a.first, b.first), add2(a.second, b.second)};
}

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int p(int a, int b){
    return a + rng()%(b-a+1);
}
/*
struct Tree{
    vector<T>tab;
    int size = 1;

    Tree(int n, string&s){
        while (size < n) size*=2;
        tab.assign(2*size, {0, 0});
    }

    void update(int x, T v){
        x += size;
        tab[x] = v;
        while (x){
            x/=2;
            tab[x] = f(tab[2*x], tab[2*x+1]);
        }
    }

    T query(int l, int r){
        T ans = {0, 0};
        for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
            if (!(l&1)) ans = f(ans, tab[l+1]);
            if (r&1) ans = f(ans, tab[r-1]);
        }
        return ans;
    }
};
*/

set<vector<int>>now;
vector<int>A, B, C;

int change(char c){
    if (c == 'J') return 0;
    else if (c == 'O') return 1;
    return 2;
}

void gen(string s, vector<int>&a){
    for (auto c: s){
        a.emplace_back(change(c));
    }
}

vector<int> merge(vector<int>&a, vector<int>&b){
    vector<int>ret;
    for (int i = 0; i<(int)a.size(); i++){
        ret.emplace_back((2*a[i] + 2*b[i])%3);
    }
    return ret;
}

struct Q{
    int l, r, c;
    T h;
    Q(){}
    Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
    bool operator <(const Q&he) const {
        return l < he.l;
    }
};

void rec(vector<int>s){
    if (now.find(s) != now.end()) return;
    now.insert(s);
    for (auto t: {A, B, C}){
        rec(merge(s, t));
    }
}

int sub2(int a, int b){
    sub(a, b);
    return a;
}

T fsub(T a, T b){
    return {sub2(a.first, b.first), sub2(a.second, b.second)};
}

void solve(){
    int n; cin >> n;
    string a, b, c; cin >> a >> b >> c;
    gen(a, A);
    gen(b, B);
    gen(c, C);
    for (auto s: {A, B, C}) rec(s);
    assert((int)now.size() <= 9);
    vector<T>Hash;
    int b1 = p(1, mod-1), b2 = p(1, mod-1);
    T p = {1, 1};
    for (auto vt: now){
        T H = {0, 0};
        // debug(vt);
        p = {1, 1};
        for (auto ch: vt){
            H = f(H, {mul(ch, p.first), mul(ch, p.second)});
            p = {mul(p.first, b1), mul(p.second, b2)};
            // debug(H);
        }
        Hash.emplace_back(H);
    }
    int q; cin >> q >> a;
    A.clear(); gen(a, A);
    set<Q>blocks;
    int begin = 0;
    T sum = {0, 0}, all = {0, 0};
    p = {1, 1};
    for (int i = 0; i<n; i++){
        if (i && A[i] != A[i-1]){
            blocks.insert({begin, i-1, sum, A[i-1]});  
            begin = i;
            sum = {0, 0};
        } 
        sum = f(sum, {mul(A[i], p.first), mul(A[i], p.second)});
        all = f(all, {mul(A[i], p.first), mul(A[i], p.second)});
        p = {mul(p.first, b1), mul(p.second, b2)};
    }
    blocks.insert({begin, n-1, sum, A.back()});
    // for (auto [l, r, h, c]: blocks){
    //     debug(l, r, h, c);
    // }
    auto answer = [&](){
        for (auto x: Hash){
            if (x == all){
                cout << "Yes\n";
                return;
            }
        }
        cout << "No\n";
    };
    debug(all);
    answer();

    vector<int>power1(n+1), power2(n+1);
    vector<int>pref1(n+1), pref2(n+1);
    power1[0] = power2[0] = 1;
    pref1[0] = pref2[0] = 1;
    for (int i = 1; i<=n; i++){
        power1[i] = mul(power1[i-1], b1);
        power2[i] = mul(power2[i-1], b2);
        pref1[i] = add2(pref1[i-1], power1[i]);
        pref2[i] = add2(pref2[i-1], power2[i]);
    }
    auto get_sum = [&](int l, int r, int v)->T {
        if (r < l) return T{0ll, 0ll};
        T ret;
        ret.first = mul(power1[l], mul(v, pref1[r-l]));
        ret.second = mul(power2[l], mul(v, pref2[r-l]));
        return ret;
    };

    while (q--){
        int l, r; char d; cin >> l >> r >> d;
        --l;--r;
        debug(l, r, d);
        int what = change(d);
        auto wrr = prev(blocks.upper_bound({l, -oo, {-oo, -oo}, -oo}));
        vector<Q>change;
        vector<int>fix;
        for (auto it = wrr; it != blocks.end() && it->l <= r; it++){
            auto [ll, rr, val, hh] = *it;
            fix.emplace_back(ll);
            // debug(ll, rr, val, hh);
            if (ll >= l && rr <= r){
                all = fsub(all, hh);
            } else {
                //at most two such intervals
                bool sub = 0;
                if (ll < l){
                    change.emplace_back(ll, l-1, get_sum(ll, l-1, val), val);
                    all = fsub(all, get_sum(l, min(rr, r), val));
                    sub = 1;
                }
                if (rr > r){
                    change.emplace_back(r+1, rr, get_sum(r+1, rr, val), val);
                    if (!sub){
                        all = fsub(all, get_sum(max(ll, l), r, val));
                    }
                }
            }
        }
        debug(all);
        change.emplace_back(l, r, get_sum(l, r, what), what);
        for (auto x: fix){
            blocks.erase(blocks.lower_bound({x, -oo, {-oo, -oo}, -oo}));
        }
        all = f(all, get_sum(l, r, what));
        for (auto x: change) {
            blocks.insert(x);
        }
        // for (auto [l, r, val, hh]: blocks){
        //     debug(l, r, val, hh);
        // }
        debug(all);
        answer();
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Compilation message (stderr)

Main.cpp: In constructor 'Q::Q(long long int, long long int, T, long long int)':
Main.cpp:114:7: warning: 'Q::h' will be initialized after [-Wreorder]
  114 |     T h;
      |       ^
Main.cpp:113:15: warning:   'long long int Q::c' [-Wreorder]
  113 |     int l, r, c;
      |               ^
Main.cpp:116:5: warning:   when initialized here [-Wreorder]
  116 |     Q(int _l, int _r, T _h, int _c): l(_l), r(_r), h(_h), c(_c) {}
      |     ^

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