Submission #503442

#	Time	Username	Problem	Language	Result	Execution time	Memory
503442		DanerZein	Crossing (JOI21_crossing)	C++14	3 / 100	732 ms	19592 KiB

Main

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

const int MAX_N=8e5+10;
const ll mod=1e9+9;
string sa,sb,sc,t;
vector<int> x;
int n;
ll tr[MAX_N],la[MAX_N],spot[MAX_N];
map<char,int> dic;
vector<ll> pot;

void init(int node,int a,int b){
  if(a==b){
    tr[node]=(x[a]*pot[a]);
    la[node]=-1;
    spot[node]=pot[a];
    return;
  }
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  init(le,a,mid);
  init(ri,mid+1,b);
  tr[node]=tr[le]+tr[ri]; tr[node]%=mod;
  spot[node]=spot[le]+spot[ri]; spot[node]%=mod;
  la[node]=-1;
}
void propagar(int node){
  if(la[node]==-1) return;
  int le=2*node+1,ri=2*node+2;
  la[ri]=la[le]=la[node];
  tr[node]=la[node]*spot[node]; tr[node]%=mod;
  la[node]=-1;
  return;
}
void update(int node,int a,int b,int l,int r,int val){
  propagar(node);
  if(a>r || b<l) return;
  if(l<=a && r>=b){
    la[node]=val;
    propagar(node);
    return;
  }
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  update(le,a,mid,l,r,val);
  update(ri,mid+1,b,l,r,val);
  tr[node]=tr[le]+tr[ri]; tr[node]%=mod;
}

int main(){
  dic['J']=0;
  dic['O']=1;
  dic['I']=2;
  cin>>n;
  pot.push_back(1);
  for(int i=1;i<n;i++){
    pot.push_back(pot[i-1]*5);
    pot[i]%=mod;
  }
  cin>>sa>>sb>>sc;
  int q; cin>>q;
  cin>>t;
  ll so=0;
  for(int i=0;i<n;i++){
    so=(so+dic[sa[i]]*pot[i])%mod;
    x.push_back(dic[t[i]]);
  }
  init(0,0,n-1);
  /* for(int i=0;i<=4;i++) cout<<tr[i]<<" ";
  cout<<endl;*/
  if(sa==t) cout<<"Yes\n";
  else cout<<"No\n";
  for(int i=0;i<q;i++){
    int l,r;
    char ch;
    cin>>l>>r>>ch;
    l--; r--;
    update(0,0,n-1,l,r,dic[ch]);
    /*cout<<tr[0]<<endl;
    for(int j=0;j<=4;j++) cout<<tr[j]<<" ";
    cout<<endl;
    for(int j=0;j<=4;j++) cout<<la[j]<<" ";
    cout<<endl;*/
    if(tr[0]==so) cout<<"Yes\n";
    else cout<<"No\n";
  }
}

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