Submission #1291796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291796		tralalero_tralala	Crossing (JOI21_crossing)	C++20	100 / 100	6151 ms	1019212 KiB

Main

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fore(i,a,b) for(lli i = (a), abcdxd = (b); i < abcdxd; i++)
#define f first
#define s second
#define pb push_back
#define ENDL '\n'
#define sz(s) lli((s).size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using namespace std;
typedef long long lli;
typedef pair<lli,lli> ii;
typedef vector<lli> vi;
typedef vector<ii> vii;
typedef long double ld;
#define deb(x) cout << #x << ": " << x << endl;

map<char, lli> mp = {{'J', 0}, {'O', 1}, {'I', 2}};
string ch = "JOI";

lli n;

string merg(string a, string b){
  // cout << a << ' ' << b << ": ";
  fore(i,0,n) if (a[i] != b[i]){
    if ('J' != a[i] and 'J' != b[i]) a[i] = 'J';
    else if ('O' != a[i] and 'O' != b[i]) a[i] = 'O';
    else if ('I' != a[i] and 'I' != b[i]) a[i] = 'I';
  }
  // cout << a << endl;
  return a;
}

struct Segt{
  #define left(u) (u + u + 1)
  #define right(u) (u + u + 2)
  #define mid ((r + l) / 2)

  struct Node{
    vi v;
    lli lazy;
    lli ans;
    Node () : v(3, 0), lazy(-1), ans(0) {}
    Node operator + (const Node& n) {
      Node tmp;
      fore(tk,0,3) tmp.v[tk] = v[tk] + n.v[tk];
      tmp.ans = ans + n.ans;
      return tmp;
    }
  };

  vector<Node> st;

  void init(lli u, lli l, lli r, string& s){
    if (l == r){
      st[u].v[mp[s[l]]]++;
      // cout << l << ' ' << st[u].v[0] << ' ' << st[u].v[1] << ' ' << st[u].v[2] << endl;
      return;
    }
    init(left(u), l, mid, s); init(right(u), mid + 1, r, s);
    st[u] = st[left(u)] + st[right(u)];
  }

  Segt (string s) : st(4 * sz(s)) {
    init(0, 0, sz(s) - 1, s);
    // cout << s << ' ' << st[0].v[0] << ' ' << st[0].v[1] << ' ' << st[0].v[2] << endl;
  }

  void push(lli u, lli l, lli r){
    if (st[u].lazy >= 0){
      if (l != r){
        st[left(u)].lazy = st[u].lazy;
        st[right(u)].lazy = st[u].lazy;
      }
      st[u].ans = st[u].v[st[u].lazy];
      st[u].lazy = -1;
    }
  }

  void update(lli u, lli l, lli r, lli ll, lli rr, lli o){
    push(u, l, r);
    // cout << u << ": " << l << ' ' << r << endl;
    // cout << ">> " << ll << ' ' << rr << endl;
    if (r < l or r < ll or rr < l or rr < ll) return;
    if (ll <= l and r <= rr){
      // cout << l << ' ' << r << ": " << ch[o] << endl;
      // cout << st[u].v[o] << endl;
      st[u].lazy = o;
      push(u, l, r);
      return;
    }
    update(left(u), l, mid, ll, rr, o); update(right(u), mid + 1, r, ll, rr, o);
    st[u] = st[left(u)] + st[right(u)];
    // cout << ":: " << u << ' ' << st[u].ans << ": " << "{" << left(u) << ", " << st[left(u)].ans << "} {" << right(u) << ", " << st[right(u)].ans << "}" << endl;
  }
};

void solve(){
  cin >> n;
  string A, B, C; cin >> A >> B >> C;
  vector<Segt> v = {Segt(A), Segt(B), Segt(C), Segt(merg(A, B)), Segt(merg(A, C)), Segt(merg(B, C)), Segt(merg(A, merg(B, C))), Segt(merg(B, merg(A, C))), Segt(merg(C, merg(A, B)))};
  lli q; cin >> q;
  string s; cin >> s;
  fore(i,0,9) fore(j,0,n){
    // deb(i);
    v[i].update(0, 0, n-1, j, j, mp[s[j]]);
  }
  bool y = false;
  fore(i,0,9){
    // cout << i << ' ' << v[i].st[0].ans << endl;
    if (v[i].st[0].ans == n) y = true;
  }
  cout << (y ? "Yes" : "No") << endl;
  fore(i,0,q){
    lli l, r; char c;
    cin >> l >> r >> c; l--, r--;
    fore(i,0,9){
      // deb(i);
      v[i].update(0, 0, n-1, l, r, mp[c]);
    }
    bool y = false;
    fore(i,0,9){
      // cout << i << ' ' << v[i].st[0].ans << endl;
      if (v[i].st[0].ans == n) y = true;
    }
    cout << (y ? "Yes" : "No") << endl;
  }
}

int main(){ _
  // freopen("tracing.in", "r", stdin);
  // freopen("tracing.out", "w", stdout);
  // lli t; cin >> t;
  // while (t--)
    solve();
  return 0;
}

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