oj.uz

Submission #429046

# Submission time Handle Problem Language Result Execution time Memory
429046 2021-06-15T17:00:06 Z DanerZein Crossing (JOI21_crossing) C++14
0 / 100
 543 ms 4872 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 tr[MAX_N*4];
int la[MAX_N*4];
vector<ll> pi;
vector<ll> su;
void init(int node,int a,int b){
  if(a==b){
    la[node]=-1;
    tr[node]=(val[a]*pi[a]*1LL)%mod;
    return;
  }
  index;
  init(le,a,mid);
  init(ri,mid+1,b);
  tr[node]=tr[le]+tr[ri];
  tr[node]%=mod;
  la[node]=-1;
}
void propagar(int node,int a,int b){
  if(la[node]==-1) return;
  ll sl,sr;
  if(a==0) sl=0;
  else sl=su[a-1];
  sr=su[b];
  tr[node]=(1LL*la[node]*(sr-sl))%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);
  tr[node]=tr[le]+tr[ri];
  tr[node]%=mod;
}
int main(){
  su.push_back(1);
  pi.push_back(1);
  for(int i=1;i<=MAX_N;i++){
    pi.push_back((pi[i-1]*(ll)5)%mod);
    su.push_back((su[i-1]+pi[i])%mod);
  }
  int n,q;
  string sa,sb,sc;
  cin>>n>>sa>>sb>>sc;
  string t0;
  cin>>q>>t0;
  ll s=0;
  map<char,int> mapeo;
  mapeo['J']=0;
  mapeo['O']=1;
  mapeo['I']=2;
  for(int i=0;i<n;i++){
    s+=(pi[i]*mapeo[sa[i]]*1LL);
    s%=mod;
    val[i]=mapeo[t0[i]];
  }
  init(0,0,n-1);
  if(s==tr[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==tr[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:35:3: note: in expansion of macro 'index'
   35 |   index;
      |   ^~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 4156 KB Output is correct
2 Correct 543 ms 4180 KB Output is correct
3 Correct 484 ms 4204 KB Output is correct
4 Correct 462 ms 4120 KB Output is correct
5 Correct 484 ms 4188 KB Output is correct
6 Correct 466 ms 4220 KB Output is correct
7 Correct 486 ms 4872 KB Output is correct
8 Incorrect 492 ms 4840 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 4156 KB Output is correct
2 Correct 543 ms 4180 KB Output is correct
3 Correct 484 ms 4204 KB Output is correct
4 Correct 462 ms 4120 KB Output is correct
5 Correct 484 ms 4188 KB Output is correct
6 Correct 466 ms 4220 KB Output is correct
7 Correct 486 ms 4872 KB Output is correct
8 Incorrect 492 ms 4840 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 4156 KB Output is correct
2 Correct 543 ms 4180 KB Output is correct
3 Correct 484 ms 4204 KB Output is correct
4 Correct 462 ms 4120 KB Output is correct
5 Correct 484 ms 4188 KB Output is correct
6 Correct 466 ms 4220 KB Output is correct
7 Correct 486 ms 4872 KB Output is correct
8 Incorrect 492 ms 4840 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 4156 KB Output is correct
2 Correct 543 ms 4180 KB Output is correct
3 Correct 484 ms 4204 KB Output is correct
4 Correct 462 ms 4120 KB Output is correct
5 Correct 484 ms 4188 KB Output is correct
6 Correct 466 ms 4220 KB Output is correct
7 Correct 486 ms 4872 KB Output is correct
8 Incorrect 492 ms 4840 KB Output isn't correct
9 Halted 0 ms 0 KB -