Submission #853778

#	Time	Username	Problem	Language	Result	Execution time	Memory
853778		Gtudor	Crossing (JOI21_crossing)	C++14	0 / 100	176 ms	20824 KiB

Main

#include <iostream>

#define NMAX 200000
using namespace std;

//ifstream cin(".in");
//ofstream cout(".out");

string s[10], t;

void add2Strings(int a, int b, int sum, int n) {
  s[sum].resize(n + 1, 0);
  s[sum][0] = ' ';
  for(int i = 1; i <= n; i++) {
    if(s[a][i] == s[b][i]) {
      s[sum][i] = s[a][i];
    } else {
      if('J' != s[a][i] && 'J' != s[b][i])
        s[sum][i] = 'J';
      if('O' != s[a][i] && 'O' != s[b][i])
        s[sum][i] = 'O';
      if('I' != s[a][i] && 'I' != s[b][i])
        s[sum][i] = 'I';
   }
  }
}

void buildAllPosStrings(int n) {
  add2Strings(1, 2, 4, n);
  add2Strings(2, 3, 5, n);
  add2Strings(3, 1, 6, n);
  add2Strings(4, 3, 7, n);
  add2Strings(5, 1, 8, n);
  add2Strings(6, 2, 9, n);
}

struct node{
  bool equal;
  char lazy, specialProp;
}arboriAint[10][NMAX * 4];

void buildArb(int indexS, int p, int lInt, int rInt) {
  if(lInt == rInt) {
    if(s[indexS][lInt] == t[lInt]) {
      arboriAint[indexS][p].equal = 1;
    }
    arboriAint[indexS][p].specialProp = s[indexS][lInt];
    return;
  }

  int med = (lInt + rInt) / 2;

  buildArb(indexS, p * 2, lInt, med);
  buildArb(indexS, p * 2 + 1, med + 1, rInt);
  
  if(arboriAint[indexS][p * 2].equal == arboriAint[indexS][p * 2 + 1].equal && arboriAint[indexS][p * 2].equal == 1)
    arboriAint[indexS][p].equal = 1;
  if(arboriAint[indexS][p * 2].specialProp == arboriAint[indexS][p * 2 + 1].specialProp)
    arboriAint[indexS][p].specialProp = arboriAint[indexS][p * 2].specialProp;
}

void propagate(node aint[], int p) {
  if(aint[p].lazy == 0)
    return;
  aint[p * 2].lazy = aint[p].lazy;
  aint[p * 2 + 1].lazy = aint[p].lazy;
  aint[p * 2].equal = ((aint[p * 2].specialProp == aint[p].lazy) && (aint[p].lazy != 0));
  aint[p * 2 + 1].equal = ((aint[p * 2 + 1].specialProp == aint[p].lazy && (aint[p].lazy != 0)));
  aint[p].lazy = 0;
}

void update(node aint[], int p, int lInt, int rInt, int lTarget, int rTarget, char modValue) {
  if(lInt == rInt) {
    aint[p].equal = (modValue == aint[p].specialProp);
    return;
  }
  propagate(aint, p);
  if(lTarget <= lInt && rInt <= rTarget) {
    aint[p].equal = (modValue == aint[p].specialProp);
    aint[p].lazy = modValue;
    return;
  }

  int med = (lInt + rInt) / 2;

  if(lTarget <= med) {
    update(aint, p * 2, lInt, med, lTarget, rTarget, modValue);
  }
  if(med + 1 <= rTarget) {
    update(aint, p * 2 + 1, med + 1, rInt, lTarget, rTarget, modValue);
  }

  aint[p].equal = ((aint[p * 2].equal == aint[p * 2 + 1].equal) && aint[p * 2].equal == 1);
}

bool isEqual(node aint[]) {
  return aint[1].equal;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q, l, r, i;
  char ch;
  bool match;

  cin>>n;

  cin>>s[1];
  s[1] = " " + s[1];
  cin>>s[2];
  s[2] = " " + s[2];
  cin>>s[3];
  s[3] = " " + s[3];

  buildAllPosStrings(n);

  cin>>q;
  cin>>t;
  t = " " + t;

  for(i = 1; i <= 9; i++) {
    buildArb(i, 1, 1, n);
  }

  match = 0;
  for(i = 1; i <= 9; i++) {
    if(isEqual(arboriAint[i]) == 1) {
      match = 1;
    }
  }
  if(match) {
    cout<<"YES\n";
  } else {
    cout<<"NO\n";
  }

  while(q--) {
    cin>>l>>r>>ch;

    for(i = 1; i <= 9; i++) {
      update(arboriAint[i], 1, 1, n, l, r, ch);
    }
    match = 0;
    for(i = 1; i <= 9; i++) {
      if(isEqual(arboriAint[i]) == 1) {
        match = 1;
      }
    }
    if(match) {
      cout<<"YES\n";
    } else {
      cout<<"NO\n";
    }
  }

  return 0;
}

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