Submission #1164913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164913		Zero_OP	Crossing (JOI21_crossing)	C++20	100 / 100	525 ms	50488 KiB

Main

//solution : number of combinations <= 9
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r) - 1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define sum_of(v) accumulate(all(v), 0ll)
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vl = vector<ll>;
using vd = vector<db>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 2e5 + 5;

int N, Q, num;
string S[3], T;
vector<string> candidates;

bool is_equal[9][MAX << 2];
bool same_all[3][9][MAX << 2];
int lazy[9][MAX << 2];

char g(char a, char b){
      if(a == b) return a;
      if(a != 'J' && b != 'J') return 'J';
      if(a != 'O' && b != 'O') return 'O';
      if(a != 'I' && b != 'I') return 'I';
      assert(false);
}

string f(string& a, string& b){
      string c = "";
      assert(sz(a) == sz(b));
      FOR(i, 0, sz(a)){
            c.pb(g(a[i], b[i]));
      }
      return c;
}

void build(int id, int l, int r){
      if(l == r){
            FOR(ids, 0, num){
                  if(candidates[ids][l] == 'J') same_all[0][ids][id] = 1;
                  if(candidates[ids][l] == 'O') same_all[1][ids][id] = 1;
                  if(candidates[ids][l] == 'I') same_all[2][ids][id] = 1;
                  is_equal[ids][id] = (candidates[ids][l] == T[l]);
            }
      } else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);

            FOR(ids, 0, num){
                  FOR(i, 0, 3) same_all[i][ids][id] = same_all[i][ids][id << 1] & same_all[i][ids][id << 1 | 1];
                  is_equal[ids][id] = is_equal[ids][id << 1] & is_equal[ids][id << 1 | 1];
            }
      }
}

bool ok(){
      FOR(i, 0, num) if(is_equal[i][1]) return 1;
      return 0;
}

void apply(int ids, int id, int v){
      is_equal[ids][id] = same_all[v][ids][id];
      lazy[ids][id] = v;
}

void down(int ids, int id){
      if(lazy[ids][id] != -1){
            apply(ids, id << 1, lazy[ids][id]);
            apply(ids, id << 1 | 1, lazy[ids][id]);
            lazy[ids][id] = -1;
      }
}

void update(int id, int l, int r, int u, int v, char c){
      if(u <= l && r <= v){
            FOR(ids, 0, num) apply(ids, id, (c == 'J' ? 0 : (c == 'O' ? 1 : 2)));
      } else{
            int mid = l + r >> 1;
            FOR(ids, 0, num) down(ids, id);
            if(u <= mid) update(id << 1, l, mid, u, v, c);
            if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, c);
            FOR(ids, 0, num) is_equal[ids][id] = is_equal[ids][id << 1] & is_equal[ids][id << 1 | 1];
      }
}

int main(){
      setIO();

      cin >> N >> S[0] >> S[1] >> S[2];
      cin >> Q >> T;

      candidates.pb(S[0]); //0
      candidates.pb(S[1]); //1
      candidates.pb(S[2]); //2

      candidates.pb(f(S[0], S[1])); //3
      candidates.pb(f(S[0], S[2])); //4
      candidates.pb(f(S[1], S[2])); //5

      candidates.pb(f(S[0], candidates[5]));
      candidates.pb(f(S[1], candidates[4]));
      candidates.pb(f(S[2], candidates[3]));

      sort(all(candidates)); compact(candidates);
      num = sz(candidates);
      build(1, 0, N-1);
      memset(lazy, -1, sizeof(lazy));

      cout << (ok() ? "Yes\n" : "No\n");
      while(Q--){
            int l, r; char c;
            cin >> l >> r >> c;
            --l, --r;
            update(1, 0, N-1, l, r, c);
            cout << (ok() ? "Yes\n" : "No\n");
      }

      return 0;
}

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