Submission #601493

#	Time	Username	Problem	Language	Result	Execution time	Memory
601493		MohammadAghil	Crossing (JOI21_crossing)	C++17	100 / 100	1922 ms	92076 KiB

Main

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) begin(x), end(x)
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     // #ifndef ONLINE_JUDGE
     //      freopen("in.in", "r", stdin);
     //      freopen("out.out", "w", stdout);
     // #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 5e5 + 5, lg = 22, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
 
struct SEG{
     vector<int> s, t; int n;
     vector<int> exp, laz;
     vector<bool> seg;

     SEG(){}

     SEG(vector<int> s, vector<int> t): s(s), t(t){
          n = sz(s);
          exp.resize(n<<2), seg.resize(n<<2);
          laz.assign(n<<2, -1);
          build(1, 0, n);
     }

     void build(int x, int lx, int rx){
          if(lx + 1 == rx){
               exp[x] = s[lx], seg[x] = s[lx] == t[lx];
               return;
          }
          int mid = (lx + rx)>>1;
          build(x<<1, lx, mid), build(x<<1|1, mid, rx);
          seg[x] = seg[x<<1]&seg[x<<1|1];
          if(exp[x<<1] == -1 || exp[x<<1|1] == -1 || exp[x<<1] - exp[x<<1|1]) exp[x] = -1;
          else exp[x] = exp[x<<1];
     }

     void updNode(int x, int k){
          seg[x] = exp[x] == k;
          laz[x] = k;
     }

     void shift(int x){
          if(laz[x] + 1){
               updNode(x<<1, laz[x]), updNode(x<<1|1, laz[x]);
               laz[x] = -1;
          }
     }

     void upd(int l, int r, int k, int x, int lx, int rx){
          if(l <= lx && r >= rx){
               updNode(x, k);
               return;
          }
          shift(x);
          int mid = (lx + rx)>>1;
          if(l < mid) upd(l, r, k, x<<1, lx, mid);
          if(mid < r) upd(l, r, k, x<<1|1, mid, rx);
          seg[x] = seg[x<<1]&seg[x<<1|1];
     }

     void upd(int l, int r, int k){ upd(l, r, k, 1, 0, n); }

     bool get(){
          return seg[1];
     }

     vector<int> gt, tg;
     void dfs(int x, int lx, int rx){
          if(lx + 1 == rx) {
               gt.pb(laz[x]), tg.pb(exp[x]);
               return;
          }
          shift(x);
          int mid = (lx + rx)>>1;
          dfs(x<<1, lx, mid), dfs(x<<1|1, mid, rx);
     }
     void dfs(){
          gt.clear(), tg.clear();
          dfs(1, 0, n);
     }
};

vector<int> comb(vector<int> a, vector<int> b){
     vector<int> res = a;
     rep(i,0,sz(a)) res[i] = (6 - a[i] - b[i])%3;
     return res;
}
 
int ID(char c){
     if(c == 'J') return 0;
     if(c == 'O') return 1;
     return 2;
}

string inv(vector<int> t){
     string res;
     for(int c: t){
          if(c == 0) res.pb('J');
          if(c == 1) res.pb('O');
          if(c == 2) res.pb('I');
     }
     return res;
}

int main(){ IOS();
     int n; cin >> n;
     vector<int> s[4];
     rep(i,0,3){
          string t; cin >> t;
          for(char c: t) s[i].pb(ID(c));
     }
     
     int q; cin >> q;
     vector<int> t;
     string tmp; cin >> tmp;
     for(char c: tmp) t.pb(ID(c));

     set<vector<int>> st;
     vector<SEG> sg;
     
     vector<vector<int>> dq;
     rep(i,0,3) st.insert(s[i]), dq.pb(s[i]), sg.pb(SEG(s[i], t));

     while(sz(dq)){
          vector<int> r = dq.back(); dq.pop_back();
          rep(i,0,3){
               vector<int> x = comb(r, s[i]);
               if(st.find(x) == end(st)) st.insert(x), dq.pb(x), sg.pb(SEG(x, t));
          }
     }


     bool ans = false;
     rep(i,0,sz(sg)) ans |= sg[i].get();
     cout << (ans? "Yes\n": "No\n");

     while(q--){
          int l, r; char c; cin >> l >> r >> c; l--;
          int id = ID(c);

          bool ans = false;
          rep(i,0,sz(sg)) sg[i].upd(l, r, id), ans |= sg[i].get();
          
          cout << (ans? "Yes\n": "No\n");
     }
     return 0; 
}

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