Submission #861417

#	Time	Username	Problem	Language	Result	Execution time	Memory
861417		vjudge1	Crossing (JOI21_crossing)	C++17	100 / 100	218 ms	17844 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 + 13, base = 23;
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 Sgt {
#define ls (idx<<1)
#define rs (idx<<1|1)
    struct data {
        int pws, val, tag;
        data() : pws(0), val(0), tag(-1) {}
    } t[off * 2];
    void pull(int idx) {
        t[idx].pws = (t[ls].pws + t[rs].pws) % mod;
        t[idx].val = (t[ls].val + t[rs].val) % mod;
        return;
    }
    void push(int idx) {
        if (~t[idx].tag) {
            t[idx].val = 1ll * t[idx].pws * t[idx].tag % mod;

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

            t[idx].tag = ~0;
        }

        return;
    }
    void build() {
        for (int idx = off, p = 1; idx < off * 2; idx++, p = 1ll * p * base % mod) {
            t[idx].pws = p;
            t[idx].val = 1ll * p * T[idx - off] % mod;
            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;
int hsh(vector<int> cur) {
    int res = 0;

    for (int i = 0, p = 1; i < n; i++, p = 1ll * p * base % mod) {
        res = (res + 1ll * cur[i] * p) % mod;
    }

    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;
        }
    }

    set<int> st;
    st.insert(hsh(s[0]));
    st.insert(hsh(s[1]));
    st.insert(hsh(s[2]));
    st.insert(hsh(cross(s[0], s[1])));
    st.insert(hsh(cross(s[1], s[2])));
    st.insert(hsh(cross(s[0], s[2])));
    st.insert(hsh(cross(s[0], cross(s[1], s[2]))));
    st.insert(hsh(cross(s[1], cross(s[0], s[2]))));
    st.insert(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 (st.find(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);
        int val = seg.t[1].val;

        if (st.find(val) != st.end()) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
}

Compilation message (stderr)

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

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