Submission #1051789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051789		happy_node	Crossing (JOI21_crossing)	C++17	100 / 100	3057 ms	20116 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

string JOI="JOI";

vector<ll> keys;

string merge(string a, string b) {
        string c="";
        for(int i=0;i<a.size();i++) {
                if(a[i]==b[i]) c+=a[i];
                else {
                        if(a[i]!='J' && b[i]!='J') c+='J';
                        if(a[i]!='O' && b[i]!='O') c+='O';
                        if(a[i]!='I' && b[i]!='I') c+='I';
                }
        }
        return c;
}

const int MX=2e5+5, B=500, mod=998244353, P=1e9+7;

ll pw[MX], pf[MX];

ll getHash(string S) {
        ll res=0;
        for(int i=0;i<S.size();i++) {
                for(int j=0;j<3;j++) {
                        if(JOI[j]==S[i]) {
                                res+=pw[i+1]*keys[j]%mod;
                                res%=mod;
                                break;
                        }
                }
        }
        return res;
}

struct DS {
        ll lazy[MX],sum[MX],val[MX]; // activate or deactivate
        ll key;

        void push(int x) {
                if(lazy[x]==1) {
                        ll curs=0;
                        for(int i=x*B;i<(x+1)*B;i++) {        
                                val[i]=0;
                                curs+=val[i];
                                curs%=mod;
                        }
                        assert(curs==sum[x]);
                }
                if(lazy[x]==2) {
                        ll curs=0;
                        for(int i=x*B;i<(x+1)*B;i++) {        
                                val[i]=pw[i+1]*key%mod;
                                curs+=val[i];
                                curs%=mod;
                        }
                        assert(curs==sum[x]);
                }
                lazy[x]=0;
        }

        void add(int l, int r) {
                int lb=l/B;
                push(lb);

                while(l%B!=0 && l<=r) {
                        sum[lb]-=val[l];
                        val[l]=pw[l+1]*key%mod;
                        sum[lb]+=val[l];
                        sum[lb]+=mod;
                        sum[lb]%=mod;
                        l++;
                }

                if(l%B!=0) return;

                while(l%B==0 && l+B-1<=r) {
                        lazy[l/B]=2;
                        sum[l/B]=(pf[l+B]-pf[l]+mod)%mod*key%mod;
                        l+=B;
                }

                int rb=l/B;
                push(rb);
                while(l<=r) {
                        sum[rb]-=val[l];
                        val[l]=pw[l+1]*key%mod;
                        sum[rb]+=val[l];
                        sum[rb]+=mod;
                        sum[rb]%=mod;
                        l++;
                }
        }

        void del(int l, int r) {
                int lb=l/B;
                push(lb);

                while(l%B!=0 && l<=r) {
                        sum[lb]-=val[l];
                        val[l]=0;
                        sum[lb]+=val[l];
                        sum[lb]+=mod;
                        sum[lb]%=mod;
                        l++;
                }

                if(l%B!=0) return;

                while(l%B==0 && l+B-1<=r) {
                        lazy[l/B]=1;
                        sum[l/B]=0;
                        l+=B;
                }

                int rb=l/B;
                push(rb);
                while(l<=r) {
                        sum[rb]-=val[l];
                        val[l]=0;
                        sum[rb]+=val[l];
                        sum[rb]+=mod;
                        sum[rb]%=mod;
                        l++;
                }
        }

        ll f() {
                ll res=0;
                for(int i=0;i<MX;i+=B) {
                        res+=sum[i/B];
                        res%=mod;
                }
                return res;
        }
} ds[3];

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

        pw[0]=1;
        pf[0]=1;
        for(int i=1;i<MX;i++) {
                pw[i]=pw[i-1]*P%mod;
                pf[i]=(pf[i-1]+pw[i])%mod;
        }
        for(int i=0;i<3;i++) {
                keys.push_back(rng()%mod);
        }

        int N;
        cin>>N;

        string sa, sb, sc;
        cin>>sa>>sb>>sc;

        vector<string> v;
        set<string> st;

        if(!st.count(sa)) {
                v.push_back(sa);
                st.insert(sa);
        }
        if(!st.count(sb)) {
                v.push_back(sb);
                st.insert(sb);
        }
        if(!st.count(sc)) {
                v.push_back(sc);
                st.insert(sc);
        }

        while(true) {
                bool fnd=0;
                for(int i=0;i<v.size();i++) {
                        for(int j=i+1;j<v.size();j++) {
                                string c=merge(v[i],v[j]);
                                if(!st.count(c)) {
                                        fnd=true;
                                        v.push_back(c);
                                        st.insert(c);
                                }
                        }
                }
                if(!fnd) break;
        }

        set<ll> tt;
        for(auto S:st) {
                tt.insert(getHash(S));
        }

        int Q;
        cin>>Q;

        string S;
        cin>>S;

        ds[0].key=keys[0];
        ds[1].key=keys[1];
        ds[2].key=keys[2];

        for(int i=0;i<N;i++) {
                int t;
                if(S[i]=='J') t=0;
                if(S[i]=='O') t=1;
                if(S[i]=='I') t=2;
                ds[t].add(i,i);
        }

        cout<<(tt.count((ds[0].f()+ds[1].f()+ds[2].f())%mod)? "Yes":"No")<<'\n';

        for(int i=0;i<Q;i++) {
                int l,r; 
                char c;
                cin>>l>>r>>c;

                int t=0;
                for(int j=0;j<3;j++) 
                        if(JOI[j]==c) t=j;

                l--,r--;

                ds[t].add(l,r);
                for(int j=0;j<3;j++)
                        if(j!=t) ds[j].del(l,r);

                cout<<(tt.count((ds[0].f()+ds[1].f()+ds[2].f())%mod)?"Yes":"No")<<'\n';
        }
}       

Compilation message (stderr)

Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for(int i=0;i<a.size();i++) {
      |                     ~^~~~~~~~~
Main.cpp: In function 'll getHash(std::string)':
Main.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i=0;i<S.size();i++) {
      |                     ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:182:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |                 for(int i=0;i<v.size();i++) {
      |                             ~^~~~~~~~~
Main.cpp:183:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |                         for(int j=i+1;j<v.size();j++) {
      |                                       ~^~~~~~~~~
Main.cpp:211:21: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
  211 |                 int t;
      |                     ^

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