Submission #962055

#	Time	Username	Problem	Language	Result	Execution time	Memory
962055		vqpahmad	Crossing (JOI21_crossing)	C++14	100 / 100	260 ms	19564 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7, base = 131;
const int N =  1e6 + 15;
const ll inf = 1e18;
const int off = (1 << 18);
vector<int> s[3];
int T[N];
char str[N];
int n, Q;
struct modint{
	int val;
	modint(ll v=0) { val = v % mod; if (val < 0) val += mod; }
	modint operator-(modint rhs){ return modint(val-rhs.val); }
	modint operator+(modint rhs){ return modint(val+rhs.val); }
	modint operator*(modint rhs){ return modint(1ll*val*rhs.val); }
	bool operator==(modint rhs){ return val==rhs.val ;};
	operator int(){
		return val;
	}
};
struct Sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
    struct data {
        modint pws, val;
	  int tag = 0;
        data() : pws(0), val(0), tag(-1) {}
    } t[off * 2];
    void pull(int idx) {
        t[idx].pws = t[ls].pws+t[rs].pws;
        t[idx].val = t[ls].val+t[rs].val;
        return;
    }
    void push(int idx) {
        if (~t[idx].tag) {
            t[idx].val = t[idx].pws * modint(t[idx].tag);

            if (idx < off)
                t[ls].tag = t[rs].tag = t[idx].tag;

            t[idx].tag = ~0;
        }

        return;
    }
    void build() {
	    modint p = 1;
	for (int idx = off; idx < off * 2; idx++, p=p*modint(base)) {
		t[idx].pws = p;
		t[idx].val = p * modint(T[idx - off]);
		t[idx].tag = ~0;
	}
	for (int idx = off - 1; idx >= 1; idx--) {
		pull(idx);
	}
    }
    void update(int l, int r, int val, int idx = 1, int lo = 0, int hi = off) {
        push(idx);

        if (r <= lo || hi <= l)
            return;

        if (l <= lo && hi <= r) {
            t[idx].tag = val;
            push(idx);
            return;
        }

        int mi = (lo + hi) >> 1;
        update(l, r, val, ls, lo, mi);
        update(l, r, val, rs, mi, hi);
        pull(idx);
    }
#undef ls
#undef rs
} seg;
modint hsh(vector<int> cur) {
    modint res = 0;
    modint p=1;
    for (int i = 0; i < n; i++, p = p * modint(base)) {
	    res = res + modint(cur[i])*p;
    }

    return res;
}
vector<int> cross(vector<int> lhs, vector<int> rhs) {
    vector<int> cur(n);

    for (int i = 0, p = 1; i < n; i++, p = 1ll * p * base % mod) {
        int c = 0;

        if (lhs[i] == rhs[i])
            c = lhs[i];
        else if (lhs[i] != 0 && rhs[i] != 0)
            c = 0;
        else if (lhs[i] != 1 && rhs[i] != 1)
            c = 1;
        else if (lhs[i] != 2 && rhs[i] != 2)
            c = 2;

        cur[i] = c;
    }

    return cur;
}
int32_t main() {
    cin >> n;

    for (int k = 0; k < 3; k++) {
        scanf("%s", str);
        s[k].resize(n);

        for (int i = 0; i < n; i++) {
            if (str[i] == 'J')
                s[k][i] = 0;

            if (str[i] == 'O')
                s[k][i] = 1;

            if (str[i] == 'I')
                s[k][i] = 2;
        }
    }

    vector<modint> st;
    st.pb(hsh(s[0]));
    st.pb(hsh(s[1]));
    st.pb(hsh(s[2]));
    st.pb(hsh(cross(s[0], s[1])));
    st.pb(hsh(cross(s[1], s[2])));
    st.pb(hsh(cross(s[0], s[2])));
    st.pb(hsh(cross(s[0], cross(s[1], s[2]))));
    st.pb(hsh(cross(s[1], cross(s[0], s[2]))));
    st.pb(hsh(cross(s[2], cross(s[0], s[1]))));
    scanf("%d", &Q);
    scanf("%s", str);

    for (int i = 0; i < n; i++) {
        if (str[i] == 'J')
            T[i] = 0;

        if (str[i] == 'O')
            T[i] = 1;

        if (str[i] == 'I')
            T[i] = 2;
    }

    seg.build();
  if (find(all(st), seg.t[1].val)!=st.end()){
        puts("Yes");
    } else {
        puts("No");
    }

    while (Q--) {
        int L, R;
        char C;
        scanf("%d %d %c", &L, &R, &C);
        int c = 0;

        if (C == 'J')
            c = 0;

        if (C == 'O')
            c = 1;

        if (C == 'I')
            c = 2;

        seg.update(L - 1, R, c);
	  if (find(all(st), seg.t[1].val)!=st.end()){
            puts("Yes");
	  }
	  else {
		puts("No");
	  }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%s", str);
      |         ~~~~~^~~~~~~~~~~
Main.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |     scanf("%d", &Q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     scanf("%s", str);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:168:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         scanf("%d %d %c", &L, &R, &C);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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