Submission #469490

#	Time	Username	Problem	Language	Result	Execution time	Memory
469490		Jarif_Rahman	Crossing (JOI21_crossing)	C++17	100 / 100	2757 ms	23380 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const str joi = "JOI";
struct joi_segtree{
    struct node{
        bool ok;
        char c, cc;
        node(){
            c = 'J';
            cc = 'J';
            ok = 1;
        }
        node operator+(node a){
            node rt;
            rt.ok = ok&a.ok;
            if(c == a.c) rt.c = c;
            else rt.c = 'X';
            if(cc == a.cc) rt.cc = cc;
            else rt.cc = 'X';
            return rt;
        }
        void pushdown(node a){
            if(a.cc !=  cc && a.cc != 'X'){
                cc = a.cc;
                if(cc != 'X' && cc == c) ok = 1;
                else ok = 0;
            }
        }
    };
    int k;
    vector<node> v;
    joi_segtree(str s){
        int n = s.size();
        k = 1;
        while(k < n) k*=2;
        while(n < k) s+='J', n++;
        k*=2;
        v.resize(k, node());
        for(int i = k/2; i < k; i++){
            v[i].c = s[i-k/2];
            if(v[i].c != v[i].cc) v[i].ok = 0;
        }
        for(int i = k/2-1; i > 0; i--) v[i] = v[2*i] + v[2*i+1];
    }
    joi_segtree(){

    }
    void query(int l, int r, int nd, int a, int b, char _cc){
        if(a > r || b < l) return;
        if(a >= l && b <= r){
            v[nd].cc = _cc;
            if(v[nd].cc != 'X' && v[nd].c == v[nd].cc) v[nd].ok = 1;
            else v[nd].ok = 0;
            return;
        }
        int md = (a+b)/2;
        v[2*nd].pushdown(v[nd]);
        v[2*nd+1].pushdown(v[nd]);
        query(l, r, 2*nd, a, md, _cc);
        query(l, r, 2*nd+1, md+1, b, _cc);
        v[nd] = v[2*nd] + v[2*nd+1];
    }
    bool query(int l, int r, char C){
        query(l, r, 1, 0, k/2-1, C);
        return v[1].ok;
    }
};
struct Query{
    str s;
    joi_segtree seg;
    bool bulid(str _s, str ss){
        s = _s;
        seg = joi_segtree(s);
        for(int i = 0; i < ss.size(); i++) seg.query(i, i, ss[i]);
        return seg.v[1].ok;
    }
    bool query(int l, int r, char c){
        return seg.query(l, r, c);
    }
};
str cross(str a, str b){
    int n = a.size();
    str crs;
    for(int i = 0; i < n; i++){
        if(a[i] == b[i]) crs+=a[i];
        else for(char c: joi) if(c != a[i] && c != b[i]) crs+=c;
    }
    return crs;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n;
    int m = 3;
    vector<str> v(3);
    for(str &s: v) cin >> s;
    int cur = 1;
    while(1){
        for(int i = cur-1; i >= 0; i--){
            str s = cross(v[cur], v[i]);
            bool bl = 0;
            for(str ss: v) if(ss == s) bl = 1;
            if(!bl) v.pb(s);
        }
        if(m == v.size() && cur == m-1) break;
        m = v.size();
        cur++;
    }
    str ss; cin >> q >> ss;
    vector<Query> qq(m);
    bool bl = 0;
    for(int i = 0; i < m; i++) bl|=qq[i].bulid(v[i], ss);
    cout << (bl ? "Yes\n":"No\n");
    while(q--){
        int l, r; char c; cin >> l >> r >> c; l--, r--;
        bl = 0;
        for(int i = 0; i < m; i++) bl|=qq[i].query(l, r, c);
        cout << (bl ? "Yes\n":"No\n");
    }
}

Compilation message (stderr)

Main.cpp: In member function 'bool Query::bulid(str, str)':
Main.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i = 0; i < ss.size(); i++) seg.query(i, i, ss[i]);
      |                        ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:110:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         if(m == v.size() && cur == m-1) break;
      |            ~~^~~~~~~~~~~

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