Submission #864202

#	Time	Username	Problem	Language	Result	Execution time	Memory
864202		vjudge1	Crossing (JOI21_crossing)	C++17	100 / 100	1440 ms	97552 KiB

Main

/* DK ORZ! */
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "algorithm"
#include "cmath"
#include "vector"
#include "set"
#include "map"
#include "unordered_set"
#include "unordered_map"
#include "queue"
#include "ctime"
#include "random"
#include "cassert"
#include "complex"
#include "string"
#include "cstring"
#include "chrono"
#include "bitset"
#include "array"
#include "stack"

#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long

using namespace std;

const int mod = 998244353;
const int nax = 200000;

string T, s[3];
int n, q;
vector <string> niza;

// Kombiniraj dva stringa
string Get_String(string a, string b){
  string res = "";
  for (int i = 0; i < n; i++){
    if (a[i] != b[i]){
      if (a[i] != 'J' && b[i] != 'J')
        res += 'J';
      else if (a[i] != 'I' && b[i] != 'I')
        res += 'I';
      else
        res += 'O';
    }else
      res += a[i];
  }
  return res;
}


struct Segment_Tree{
  pair <int,char> t[nax * 3];
  char Lazy[nax * 3];
  int index = 0;

  void push(int k, int l, int r){
    if (l == r || Lazy[k] == 'z')return;
    t[k].first = (t[k].second == Lazy[k]);
    Lazy[k * 2] = Lazy[k];
    Lazy[k * 2 + 1] = Lazy[k];
    t[k * 2].first = t[k * 2].second == Lazy[k];
    t[k * 2+1].first = t[k * 2+1].second == Lazy[k];
    Lazy[k] = 'z';
  }

  void build(int l = 0, int r = n - 1, int k = 1){
    t[k].first = 0;
    t[k].second = 'z'; //debilna vrednost
    Lazy[k] = 'z';
    if (l == r){
      t[k].first = (T[l] == niza[index][l]);
      t[k].second = (niza[index][l]);
      return;
    }

    int mid = (l+r) / 2;
    build(l,mid,k*2);
    build(mid+1,r,k*2+1);

    t[k].first = (t[k * 2].first & t[k * 2 + 1].first);
    if (t[k * 2].second == t[k * 2 + 1].second)
      t[k].second = t[k * 2].second;
  }

  void update(int ll, int rr, char nova, int l = 0, int r = n - 1, int k = 1){
    push(k, l, r);
    if (l >= ll && r <= rr){
      t[k].first = (t[k].second == nova);
      Lazy[k] = nova;
      return;
    }
    if (l > rr || r < ll)return;

    int mid = (l+r) / 2;
    update(ll,rr,nova,l,mid,k*2);
    update(ll,rr,nova,mid+1,r,k*2+1);

    t[k].first = (t[k * 2].first & t[k * 2 + 1].first);
  }
};

vector <Segment_Tree> Site(9);

void solve(){
  cin >> n;
  cin >> s[0] >> s[1] >> s[2];
  for (int i = 0; i < 3; i++){
    for (int j = i; j < 3; j++){
      if (i == j)continue;
      int Third;
      if (i != 0 && j != 0)Third = 0;
      else if (i != 1 && j != 1)Third = 1;
      else Third = 2;
      niza.push_back(Get_String(s[i], s[j]));
      niza.push_back(Get_String(niza.back(), s[Third]));
    }
    niza.push_back(s[i]);
  }
  cin >> q;
  cin >> T;
  for (int i = 0; i < 9; i++){
    Site[i].index = i;
    Site[i].build();
  }

  int ok = 0;
  for (int i = 0; i < 9; i++){
    ok |= Site[i].t[1].first;
  }
  cout << (ok ? "Yes" : "No") << endl;
  while(q--){
    int l, r; 
    char v;
    cin >> l >> r >> v;
    --l,--r;
    ok = 0;
    for (int i = 0; i < 9; i++){
      Site[i].update(l,r,v);
      ok |= Site[i].t[1].first;
    }
    cout << (ok ? "Yes" : "No") << endl;
  }
}

signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

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