oj.uz

Submission #429070

# Submission time Handle Problem Language Result Execution time Memory
429070 2021-06-15T17:09:26 Z DanerZein Crossing (JOI21_crossing) C++14
0 / 100
 634 ms 7932 KB 
#include <bits/stdc++.h>
#define index int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
using namespace std;
typedef long long ll;
const int MAX_N=2e5+10;
const ll mod=1e9+9;
int val[MAX_N];
ll tr1[MAX_N*4],tr2[MAX_N];
int la[MAX_N*4];
vector<ll> pi1,pi2;
vector<ll> su1,su2;
void init(int node,int a,int b){
  if(a==b){
    la[node]=-1;
    tr2[node]=(val[a]*pi2[a]*1LL)%mod;
    tr1[node]=(val[a]*pi1[a]*1LL)%mod;
    return;
  }
  index;
  init(le,a,mid);
  init(ri,mid+1,b);
  tr1[node]=(tr1[le]+tr1[ri])%mod;
  tr2[node]=(tr2[le]+tr2[ri])%mod;
  la[node]=-1;
}
void propagar(int node,int a,int b){
  if(la[node]==-1) return;
  ll sl1,sr1,sl2,sr2;
  if(a==0){
    sl1=sl2=0;
  }
  else {
    sl1=su1[a-1];
    sl2=su2[a-1];
  }
  sr1=su1[b]; sr2=su2[b];
  tr1[node]=(1LL*la[node]*(sr1-sl1))%mod;
  tr2[node]=(1LL*la[node]*(sr2-sl2))%mod;
  int aux=la[node];
  la[node]=-1;
  if(a==b) return;
  index;
  la[le]=aux;
  la[ri]=aux;
}
void update(int node,int a,int b,int l,int r,int val){
  propagar(node,a,b);
  if(l>b || r<a) return;
  if(l<=a && r>=b){
    la[node]=val;
    propagar(node,a,b);
    return;
  }
  index;
  update(le,a,mid,l,r,val);
  update(ri,mid+1,b,l,r,val);
  tr1[node]=(tr1[le]+tr1[ri])%mod;
  tr2[node]=(tr2[le]+tr2[ri])%mod;
}
int main(){
  su1.push_back(1); su2.push_back(1);
  pi1.push_back(1); pi2.push_back(1);
  for(int i=1;i<=MAX_N;i++){
    pi1.push_back((pi1[i-1]*(ll)3)%mod);
    pi2.push_back((pi2[i-1]*(ll)31)%mod);
    su1.push_back((su1[i-1]+pi1[i])%mod);
    su2.push_back((su2[i-1]+pi2[i])%mod);
  }
  int n,q;
  string sa,sb,sc;
  cin>>n>>sa>>sb>>sc;
  string t0;
  cin>>q>>t0;
  ll s=0,s1=0;
  map<char,int> mapeo;
  mapeo['J']=0;
  mapeo['O']=1;
  mapeo['I']=2;
  for(int i=0;i<n;i++){
    s=(s+(pi1[i]*mapeo[sa[i]]*1LL))%mod;
    s1=(s1+(pi2[i]*mapeo[sa[i]]*1LL))%mod;
    val[i]=mapeo[t0[i]];
  }
  init(0,0,n-1);
  if(s==tr1[0] && s1==tr2[0]) cout<<"Yes\n";
  else cout<<"No\n";
  for(int i=0;i<q;i++){
    int l,r;
    char x;
    cin>>l>>r>>x;
    l--; r--;
    update(0,0,n-1,l,r,mapeo[x]);
    /*   for(int j=0;j<5;j++) cout<<tr[j]<<" ";
    cout<<endl;
    for(int j=0;j<5;j++) cout<<la[j]<<" ";
    cout<<endl;
    */
    if(s==tr1[0] && s1==tr2[0]) cout<<"Yes\n";
    else cout<<"No\n";
  }
}

Compilation message

Main.cpp: In function 'void propagar(int, int, int)':
Main.cpp:2:19: warning: unused variable 'mid' [-Wunused-variable]
    2 | #define index int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
      |                   ^~~
Main.cpp:42:3: note: in expansion of macro 'index'
   42 |   index;
      |   ^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 7816 KB Output is correct
2 Correct 634 ms 7892 KB Output is correct
3 Correct 571 ms 7932 KB Output is correct
4 Incorrect 535 ms 7916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 7816 KB Output is correct
2 Correct 634 ms 7892 KB Output is correct
3 Correct 571 ms 7932 KB Output is correct
4 Incorrect 535 ms 7916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 7816 KB Output is correct
2 Correct 634 ms 7892 KB Output is correct
3 Correct 571 ms 7932 KB Output is correct
4 Incorrect 535 ms 7916 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 7816 KB Output is correct
2 Correct 634 ms 7892 KB Output is correct
3 Correct 571 ms 7932 KB Output is correct
4 Incorrect 535 ms 7916 KB Output isn't correct
5 Halted 0 ms 0 KB -