Submission #661801

#	Time	Username	Problem	Language	Result	Execution time	Memory
661801		victor_gao	Crossing (JOI21_crossing)	C++17	100 / 100	400 ms	16276 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 200015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
const int mod1=233LL;
const int mod2=998244353LL;
const int inv1=844009174LL;
const int inv_mod1_1=684141604LL;
int n,p[N],inv[N];
string s1,s2,s3;
char get(char a,char b){
    if (a==b) return a;
    else if (a!='O'&&b!='O') return 'O';
    else if (a!='J'&&b!='J') return 'J';
    return 'I';
}
string cross(string a,string b){
    string ans="";
    for (int i=0;i<n;i++)
        ans.push_back(get(a[i],b[i]));
    return ans;
}
string ori;
set<int>can;
int fast_pow(int a,int b,int mod){
    int ans=1;
    while (b){
        if (b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
struct segtree{
    int seg[4*N],tag[4*N];
    void build(int l,int r,int i){
        if (l==r){
            seg[i]=(ori[l-1]-'A')*p[l-1]%mod2;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,2*i);
        build(mid+1,r,2*i+1);
        seg[i]=(seg[2*i]+seg[2*i+1])%mod2;
    }
    int count(int l,int r,char c){
        return p[l-1]*((p[r-l+1]-1+mod2)%mod2)%mod2*inv_mod1_1%mod2*(c-'A')%mod2;
    }
    void push(int l,int r,int i){
        if (tag[i]){
            int mid=(l+r)>>1;
            tag[2*i]=tag[i];
            seg[2*i]=count(l,mid,(char)(tag[i]+'A'));
            tag[2*i+1]=tag[i];
            seg[2*i+1]=count(mid+1,r,(char)(tag[i]+'A'));
            tag[i]=0;
        }
    }
    void modify(int l,int r,int i,int ll,int rr,char c){
        if (ll<=l&&rr>=r){
            tag[i]=c-'A';
            seg[i]=count(l,r,c);
            return;
        }
        int mid=(l+r)>>1;
        push(l,r,i);
        if (rr<=mid) modify(l,mid,2*i,ll,rr,c);
        else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,c);
        else {
            modify(l,mid,2*i,ll,mid,c);
            modify(mid+1,r,2*i+1,mid+1,rr,c);
        }
        seg[i]=(seg[2*i]+seg[2*i+1])%mod2;
    }
}seg;
int get_hash(string str){
    int val=0;
    for (int i=0;i<n;i++)
        val=(val+p[i]*(str[i]-'A'))%mod2;
    return val;
}
void build(){
    p[0]=1; inv[0]=1;
    for (int i=1;i<=n;i++){
        p[i]=p[i-1]*mod1%mod2;
        inv[i]=inv[i-1]*inv1%mod2;
    }
    vector<string>all;
    all.push_back(s1); all.push_back(s2); all.push_back(s3);
    set<string>st;
    for (auto i:all)
        st.insert(i);
    for (int h=0;h<2;h++){
        all.clear();
        for (auto i:st)
            all.push_back(i);
        for (int i=0;i<all.size();i++){
            for (int j=i+1;j<all.size();j++){
                string str=cross(all[i],all[j]);
                st.insert(str);
            }
        }
    }
    for (auto i:st){
        can.insert(get_hash(i));
    }
}
signed main(){
    fast
    cin>>n>>s1>>s2>>s3;
    build();
    int q; cin>>q;
    cin>>ori;
    seg.build(1,n,1);
    if (can.find(seg.seg[1])!=can.end())
        cout<<"Yes\n";
    else cout<<"No\n";
    while (q--){
        int l,r;
        char c;
        cin>>l>>r>>c;
        seg.modify(1,n,1,l,r,c);
        if (can.find(seg.seg[1])!=can.end())
            cout<<"Yes\n";
        else cout<<"No\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'void build()':
Main.cpp:109:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int i=0;i<all.size();i++){
      |                      ~^~~~~~~~~~~
Main.cpp:110:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for (int j=i+1;j<all.size();j++){
      |                            ~^~~~~~~~~~~

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