Submission #650023

#	Time	Username	Problem	Language	Result	Execution time	Memory
650023		ToroTN	Crossing (JOI21_crossing)	C++14	100 / 100	421 ms	26956 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,hsh[505],pow_97[200005],mod=1000000007,cnt,seg[800005],x,y,t,qs[200005];
char s[10][200005],op[3]={'J','O','I'},chng[5],str[200005],lz[800005];
map<ll,ll> mp;
void cross(char arr1[],char arr2[],char arr3[])
{
    for(int i=1;i<=n;i++)
    {
        if(arr1[i]==arr2[i])
        {
            arr3[i]=arr1[i];
        }else
        {
            arr3[i]=op[3-hsh[arr1[i]]-hsh[arr2[i]]];
        }
    }
}
void build(ll tree,ll st,ll ed)
{
    ll md=(st+ed)/2;
    if(st==ed)
    {
        seg[tree]=(pow_97[1]*(ll)str[st])%mod;
        //printf("%lld %lld %lld\n",st,ed,seg[tree]);
        //printf("%c\n",str[st]);
        //printf("%lld\n",pow_97[1]);
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg[tree]=(seg[2*tree]+(pow_97[md-st+1]*seg[2*tree+1])%mod)%mod;
}
void update(ll tree,ll st,ll ed,ll l,ll r,char val)
{
    ll md=(st+ed)/2;
    if(st>=l&&ed<=r)lz[tree]=val;
    if(lz[tree]!=0)
    {
        if(st!=ed)
        {
            lz[2*tree]=lz[tree];
            lz[2*tree+1]=lz[tree];
        }
        seg[tree]=(lz[tree]*qs[ed-st+1])%mod;
        lz[tree]=0;
    }
    if(st>=l&&ed<=r)
    {
        return;
    }
    if(st>r||ed<l)return;
    update(2*tree,st,md,l,r,val);
    update(2*tree+1,md+1,ed,l,r,val);
    seg[tree]=(seg[2*tree]+(pow_97[md-st+1]*seg[2*tree+1])%mod)%mod;
}
int main()
{
    hsh['J']=0,hsh['O']=1,hsh['I']=2;
    scanf("%lld",&n);
    for(int i=1;i<=3;i++)scanf("%s",s[i]+1);
    cross(s[1],s[2],s[4]);
    cross(s[1],s[3],s[5]);
    cross(s[2],s[3],s[6]);
    cross(s[3],s[4],s[7]);
    cross(s[2],s[5],s[8]);
    cross(s[1],s[6],s[9]);
    pow_97[0]=1;
    for(int i=1;i<=200000;i++)
    {
        pow_97[i]=pow_97[i-1]*97;
        pow_97[i]%=mod;
    }
    qs[1]=pow_97[1];
    for(int i=2;i<=200000;i++)
    {
        qs[i]=qs[i-1]+pow_97[i];
        qs[i]%=mod;
    }
    for(int i=1;i<=9;i++)
    {
        //printf("%d string=%s\n",i,s[i]+1);
        cnt=0;
        for(int j=1;j<=n;j++)
        {
            cnt+=(pow_97[j]*s[i][j])%mod;
            cnt%=mod;
            //printf("%lld ",cnt);
        }
        //printf("\n");
        //printf("%lld\n",cnt);
        ++mp[cnt];
    }
    //printf("\n");
    scanf("%lld",&t);
    scanf("%s",str+1);
    build(1,1,n);
    //printf("%lld\n",seg[1]);
    if(mp[seg[1]]==0)
    {
        printf("No\n");
    }else
    {
        printf("Yes\n");
    }
    while(t--)
    {
        scanf("%lld%lld%s",&x,&y,chng);
        //printf("vijak\n");
        if(lz[1]!=0)
        {
            lz[2]=lz[3]=lz[1];
            seg[1]=(qs[n]*lz[1])%mod;
            lz[1]=0;
        }
        update(1,1,n,x,y,chng[0]);
        if(mp[seg[1]]==0)
        {
            printf("No\n");
        }else
        {
            printf("Yes\n");
        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'void cross(char*, char*, char*)':
Main.cpp:16:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |             arr3[i]=op[3-hsh[arr1[i]]-hsh[arr2[i]]];
      |                              ~~~~~~^
Main.cpp:16:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   16 |             arr3[i]=op[3-hsh[arr1[i]]-hsh[arr2[i]]];
      |                                           ~~~~~~^
Main.cpp: In function 'int main()':
Main.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:62:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     for(int i=1;i<=3;i++)scanf("%s",s[i]+1);
      |                          ~~~~~^~~~~~~~~~~~~
Main.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%lld",&t);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%s",str+1);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%lld%lld%s",&x,&y,chng);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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