Submission #427738

#	Time	Username	Problem	Language	Result	Execution time	Memory
427738		DanerZein	Crossing (JOI21_crossing)	C++14	0 / 100	448 ms	2328 KiB

Main

#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 int MAX_P=MAX_N*4;
struct dato{
  int nj,no,ni;
};
bool tr[MAX_P];
char la[MAX_P];
dato ini[MAX_P],act[MAX_P];
string a,b,c,y;
dato join(dato a,dato b){
  return {a.nj+b.nj,a.no+b.no,a.ni+b.ni};
}
void init(int node,int a,int b){
  if(a==b){
    if(c[a]==y[a]) tr[node]=1;
    else tr[node]=0;
    la[node]='#';
    ini[node]=act[node]={0,0,0};
    if(c[a]=='J') ini[node].nj++;
    if(c[a]=='O') ini[node].no++;
    if(c[a]=='I') ini[node].ni++;
    if(y[a]=='J') act[node].nj++;
    if(y[a]=='O') act[node].no++;
    if(y[a]=='I') act[node].ni++;
    return;
  }
  index;
  init(le,a,mid);
  init(ri,mid+1,b);
  tr[node]=tr[le]&tr[ri];
  la[node]='#';
  ini[node]=join(ini[le],ini[ri]);
  act[node]=join(act[le],act[ri]);
}
bool igual(int a){
  if(ini[a].nj==act[a].nj && ini[a].no==act[a].no && ini[a].ni==act[a].ni) return 1;
  return 0;
}
void propagar(int node,int a,int b){
  if(la[node]=='#') return;
  char aux=la[node];
  act[node]={0,0,0};
  if(aux=='J') act[node].nj=(a-b)+1;
  if(aux=='O') act[node].no=(a-b)+1;
  if(aux=='I') act[node].ni=(a-b)+1;
  if(igual(node)){
    tr[node]=1;
  }
  la[node]='#';
  if(a==b) return;
  index;
  la[le]=aux;
  la[ri]=aux;
}
void update(int node,int a,int b,int l,int r,char 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);
  act[node]=join(act[le],act[ri]);
  tr[node]=tr[le]&tr[ri];
}
int main(){
  int n,q;
  cin>>n;
  cin>>a>>b>>c;
  cin>>q>>y;
  if(y==a) cout<<"Yes\n";
  else cout<<"No\n";
  init(0,0,n-1);
  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,x);
    if(tr[0]) cout<<"Yes\n";
    else cout<<"No\n";
  }
}

Compilation message (stderr)

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:55:3: note: in expansion of macro 'index'
   55 |   index;
      |   ^~~~~

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