Submission #558066

#	Time	Username	Problem	Language	Result	Execution time	Memory
558066		groshi	Crossing (JOI21_crossing)	C++17	26 / 100	257 ms	18252 KiB

Main

#include<iostream>

using namespace std;
string s[10];
char jaki[4]={'J','O','I'};
long long pierw=1000696969;
long long pot[300000];
long long pref[300000];
long long hasze[300000];
long long drzewo[600000];
long long lazy[600000];
int n;
char brak(char a,char b)
{
    for(int i=0;i<3;i++)
        if(jaki[i]!=a && jaki[i]!=b)
            return jaki[i];
}
void comp(int co1,int co2,int gdzie)
{
    string pom="";
    for(int i=0;i<s[co1].length();i++)
    {
        if(s[co1][i]==s[co2][i])
            pom.push_back(s[co1][i]);
        else pom.push_back(brak(s[co1][i],s[co2][i]));
    }
    s[gdzie]=pom;
}
void zrob()
{
    comp(0,1,3);
    comp(0,2,4);
    comp(1,2,5);
    comp(3,2,6);
    comp(4,1,7);
    comp(0,5,8);
}
void pie()
{
    pot[0]=1;
    for(int i=1;i<=200000;i++)
        pot[i]=pot[i-1]*pierw;
    pref[0]=1;
    for(int i=1;i<=200000;i++)
        pref[i]=pref[i-1]+pot[i];
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<s[i].length();j++)
            hasze[i]=hasze[i]+(s[i][j]-'A'+1)*pot[j];
       //cout<<hasze[i]<<"\n";
    }
}
void prop(int x,int l,int r)
{
    if(lazy[x]==0)
        return;
    //cout<<pref[r-l]<<"\n";
    drzewo[x]=(pref[r-l]*lazy[x]);
    if(l!=r)
    {
        lazy[x*2]=lazy[x];
        lazy[x*2+1]=lazy[x];
    }
    lazy[x]=0;
}
void upd(int x,int l,int r,int x1,int y1,int co)
{
    //cout<<"jestem w "<<x<<"\n";
    prop(x,l,r);
    if(x1>r || y1<l || l>r)
        return;
    if(x1<=l && r<=y1)
    {
        lazy[x]=co;
        prop(x,l,r);
        return;
    }
    int mid=(l+r)/2;
    upd(x*2,l,mid,x1,y1,co);
    upd(x*2+1,mid+1,r,x1,y1,co);
    drzewo[x]=drzewo[x*2]+drzewo[x*2+1]*pot[mid-l+1];
}
long long idz()
{
    prop(1,1,n);
    return drzewo[1];
}
bool ok()
{
    long long hasz=idz();
    //cout<<hasz<<"\n";
    for(int i=0;i<9;i++)
        if(hasz==hasze[i])
            return 1;
    return 0;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    cin>>s[0]>>s[1]>>s[2];
    zrob();
    pie();
    int zap;
    cin>>zap;
    string wzor;
    cin>>wzor;
    for(int i=1;i<=wzor.length();i++)
        upd(1,1,n,i,i,wzor[i-1]-'A'+1);
    if(ok())
        cout<<"Yes\n";
    else cout<<"No\n";
    while(zap--)
    {
        int a,b;
        char c;
        cin>>a>>b>>c;
        upd(1,1,n,a,b,c-'A'+1);
        if(ok())
            cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void comp(int, int, int)':
Main.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<s[co1].length();i++)
      |                 ~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void pie()':
Main.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<s[i].length();j++)
      |                     ~^~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:111:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i=1;i<=wzor.length();i++)
      |                 ~^~~~~~~~~~~~~~~
Main.cpp: In function 'char brak(char, char)':
Main.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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