Submission #771098

#	Time	Username	Problem	Language	Result	Execution time	Memory
771098		gagik_2007	Crossing (JOI21_crossing)	C++17	100 / 100	510 ms	19372 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=2e5+7;
ll n,m,k;
vector<string>b;
string s1,s2,s3,tt;
char vs[3]={'J', 'O', 'I'};
int vls[500];
const ll B=7;
ll powB[N];
ll powBsum[N];
ll t[4*N];
ll lazy[8*N];
vector<ll>hashes;

ll str_hash(const string& s) {
    ll ans=0;
    ll cur=1;
    for(char c:s){
        ans+=vls[c]*cur;
        ans%=MOD;
        cur*=B;
        cur%=MOD;
    }
    return ans;
}

void push(int v, int tl, int tr) {
    if(lazy[v]!=0){
        lazy[v]--;
        t[v]=lazy[v]*powB[tl]*powBsum[tr-tl];
        t[v]%=MOD;
        lazy[v]++;
        lazy[2*v]=lazy[v];
        lazy[2*v+1]=lazy[v];
        lazy[v]=0;
    }
}

void build(int v, int tl, int tr) {
    if(tl==tr){
        t[v]=vls[tt[tl]]*powB[tl];
        t[v]%=MOD;
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=t[2*v]+t[2*v+1];
        t[v]%=MOD;
    }
}

void update(int v, int tl, int tr, int l, int r, char c) {
    push(v,tl,tr);
    if(l>r)return;
    if(tl==l&&tr==r){
        lazy[v]=vls[c]+1;
        push(v,tl,tr);
    }
    else{
        push(v,tl,tr);
        int tm=(tl+tr)/2;
        update(2*v,tl,tm,l,min(r,tm),c);
        update(2*v+1,tm+1,tr,max(l,tm+1),r,c);
        t[v]=t[2*v]+t[2*v+1];
        t[v]%=MOD;
        push(v,tl,tr);
    }
}

string cross(const string& a, const string& b) {
    string c;
    for(int i=0;i<a.size();i++){
        if(a[i]==b[i]){
            c+=a[i];
        }
        else {
            c+=vs[3-vls[a[i]]-vls[b[i]]];
        }
    }
    return c;
}

bool compare(){
    for(ll h:hashes){
        if(h==t[1])return true;
    }
    return false;
}

void precalc() {
    vls['J']=0;
    vls['O']=1;
    vls['I']=2;
    powB[0]=1;
    powBsum[0]=1;
    for(int i=1;i<N;i++){
        powB[i]=powB[i-1]*B;
        powB[i]%=MOD;
        powBsum[i]=powBsum[i-1]+powB[i];
        powBsum[i]%=MOD;
    }
}

int main() {
    precalc();
    cin>>n;
    cin>>s1>>s2>>s3;
    b.push_back(s1);
    b.push_back(s2);
    b.push_back(s3);
    b.push_back(cross(s1,s2));
    b.push_back(cross(s2,s3));
    b.push_back(cross(s1,s3));
    b.push_back(cross(b[3],b[4]));
    b.push_back(cross(b[3],b[5]));
    b.push_back(cross(b[4],b[5]));
    for(string& s:b){
        hashes.push_back(str_hash(s));
    }
    cin>>m;
    cin>>tt;
    build(1,0,n-1);
    if(compare()){
        cout<<"Yes\n";
    }
    else cout<<"No\n";
    for(int i=0;i<m;i++){
        int l,r;
        char c;
        cin>>l>>r>>c;
        l--,r--;
        update(1,0,n-1,l,r,c);
        // for(int i=0;i<100;i++)cout<<t[i]<<" ";cout<<endl;
        // for(int i=0;i<100;i++)cout<<lazy[i]<<" ";cout<<endl;
        if(compare()){
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
}

Compilation message (stderr)

Main.cpp: In function 'll str_hash(const string&)':
Main.cpp:29:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   29 |         ans+=vls[c]*cur;
      |                  ^
Main.cpp: In function 'void build(int, int, int)':
Main.cpp:51:24: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |         t[v]=vls[tt[tl]]*powB[tl];
      |                        ^
Main.cpp: In function 'void update(int, int, int, int, int, char)':
Main.cpp:67:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   67 |         lazy[v]=vls[c]+1;
      |                     ^
Main.cpp: In function 'std::string cross(const string&, const string&)':
Main.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
Main.cpp:88:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |             c+=vs[3-vls[a[i]]-vls[b[i]]];
      |                             ^
Main.cpp:88:39: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |             c+=vs[3-vls[a[i]]-vls[b[i]]];
      |                                       ^

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