Submission #874970

#	Time	Username	Problem	Language	Result	Execution time	Memory
874970		efedmrlr	Crossing (JOI21_crossing)	C++17	100 / 100	244 ms	25308 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 2e5+5;
const lli MOD = 1e9+7;
const lli INF = 1e12;
const int M = 1e6+5;
const long double EPS = 0.00001;
const lli PRIME = 5;
int n,m,q;
vector<int> A,B,C;
lli pw[N];
lli powsm[N];
vector<lli> hs(9);
lli mult(lli x, lli y) {
    return x*y%MOD;
}
lli add(lli x, lli y) {
    return (x+y)%MOD;
}
lli subt(lli x, lli y) {
    if(x - y < 0) return x - y + MOD;
    return x - y;
}
lli find_pow_sum(int l, int r) {
    return subt(powsm[r] , (l > 0 ? powsm[l - 1] : 0ll));
}


struct SegTree {
    vector<lli> data, lazy;
    int sz;
    SegTree(int sz) {
        this->sz = sz;
        data.assign(4*(sz+5), 0);
        lazy.assign(4*(sz+5), -1);
    }
    void push(int tl, int tr, int v) {
        if(lazy[v] == -1) return;
        int tm = (tl + tr) >> 1;
        data[v*2] = mult(lazy[v] , find_pow_sum(tl, tm));
        data[v*2+1] = mult(lazy[v] , find_pow_sum(tm + 1, tr));
        lazy[v*2] = lazy[v];
        lazy[v*2+1] = lazy[v];
        lazy[v] = -1; 
    }

    void update(int tl, int tr, int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            lazy[v] = val;
            data[v] = mult(val , find_pow_sum(tl, tr));
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(tl, tr, v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v*2, l, r, val);
        update(tm + 1, tr ,v*2+1, l, r, val);
        data[v] = add(data[v*2], data[v*2+1]);
    }
    void update(int l, int r, int val) {
        update(0, sz - 1, 1, l, r, val);
    }
    lli query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) {
            return data[v];
        }
        if(tl > r || tr < l) {
            return 0;
        }
        push(tl, tr, v);
        int tm = (tl + tr) >> 1;
        return add(query(tl, tm, v*2, l, r), query(tm + 1, tr, v*2+1, l , r));
    }
    lli query(int l, int r) {
        return query(0, sz - 1, 1, l, r);
    }
};

void str_to_vec(string &src, vector<int> &nw) {
    nw.resize(src.size());
    for(int i = 0; i<src.size(); i++) {
        if(src[i] == 'J') nw[i] = 0;
        if(src[i] == 'O') nw[i] = 1;
        if(src[i] == 'I') nw[i] = 2;
    }
}
vector<int> cross(vector<int> &x, vector<int> &y) {
    vector<int> ret(n);
    for(int i = 0; i<n; i++) {
        int c1 = x[i],c2 = y[i];
        if(c1 > c2) swap(c1, c2);
        if(c1 == c2) {
            ret[i] = c1;
        }
        else if(c1 == 0 && c2 == 1) {
            ret[i] = 2;
        }
        else if(c1 == 1 && c2 == 2) {
            ret[i] = 0;
        }
        else if(c1 == 0 && c2 == 2) {
            ret[i] = 1;
        }
        else {
            assert(0);
        }

    }
    return ret;
}

lli find_hash(vector<int> &x) {
    lli ret = 0;
    for(int i = 0; i<n; i++) {
        ret = add(ret , mult(x[i] , pw[i]));
    }
    return ret;
}
void calc_hash() {
    hs[0] = find_hash(A);
    hs[1] = find_hash(B);
    hs[2] = find_hash(C);
    vector<int> ab = cross(A,B), ac = cross(A,C), bc = cross(B,C);
    hs[3] = find_hash(ab);
    hs[4] = find_hash(ac);
    hs[5] = find_hash(bc);
    vector<int> abC = cross(ab, C), acB = cross(ac, B), bcA = cross(bc, A);
    hs[6] = find_hash(abC);
    hs[7] = find_hash(acB);
    hs[8] = find_hash(bcA);
}
bool check(lli x) {
    for(auto ind : hs) {
        if(x == ind) return 1;
    }
    return 0;
}
signed main() {
    //PREC
    powsm[0] = 1ll;
    pw[0] = 1ll;
    for(int i = 1; i<N; i++) {
        pw[i] = mult(pw[i - 1], PRIME);
        powsm[i] = powsm[i - 1] + pw[i];
    }
    fastio();
    cin>>n;
    string tmp;
    cin>>tmp;
    str_to_vec(tmp, A);
    cin>>tmp;
    str_to_vec(tmp, B);
    cin>>tmp;
    str_to_vec(tmp, C);

    cin>>q;
    vector<int> t0;
    cin>>tmp;
    str_to_vec(tmp, t0);
    SegTree st(n);
    calc_hash();
    for(int i = 0; i<n; i++) {
        st.update(i, i, t0[i]);
    }
    if(check(st.query(0, n - 1))) {
        cout<<"Yes\n";
    }
    else {
        cout<<"No\n";
    }
    for(int i = 0; i<q; i++) {
        int l,r, cr;
        char c;
        cin>>l>>r>>c;
        l--; r--;
        if(c == 'J') cr = 0;
        if(c == 'O') cr = 1;
        if(c == 'I') cr = 2;
        st.update(l,r,cr);
        lli tmp = st.query(0, n - 1);
        if(check(tmp)) {
            cout<<"Yes\n";
        }
        else {
            cout<<"No\n";
        }
        
        
    }


}

Compilation message (stderr)

Main.cpp: In function 'void str_to_vec(std::string&, std::vector<int>&)':
Main.cpp:95:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0; i<src.size(); i++) {
      |                    ~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:61:23: warning: 'cr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |             lazy[v] = val;
      |                       ^~~
Main.cpp:186:18: note: 'cr' was declared here
  186 |         int l,r, cr;
      |                  ^~

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