Submission #891301

#	Time	Username	Problem	Language	Result	Execution time	Memory
891301		coldEr66	Crossing (JOI21_crossing)	C++17	0 / 100	360 ms	35760 KiB

Main

#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

char JOI[] = {'J', 'O', 'I'};

vector<int> cross(vector<int> &g1, vector<int> &g2) {
    vector<int> ret;
    for (int i = 0; i < SZ(g1); ++i) {
        int cur = 2 * (g1[i] + g2[i]) % 3;
        ret.eb(cur);
    }
    return ret;
}

const int maxn = 2e5 + 5;

int sc[maxn * 4];

struct S {
    int c, val, id;
    S() : c(-1), val(0), id(-1) {}
    S(int _c, int _val, int _id) : c(_c), val(_val), id(_id) {}
};
struct F {
    int c;
    F() : c(-1) {}
    F(int _c) : c(_c) {}
};
S seg[maxn * 4];
F tag[maxn * 4];

S opr(S l, S r) {
    int c, val;
    if (l.c == -1 || r.c == -1) c = -1;
    else if (l.c == r.c) c = l.c;
    else c = -1;

    val = l.val & r.val;
    return S(c, val, (l.id - 1) / 2);
}

S M(F f, S s) {
    if (f.c == -1) return s;
    s.c = f.c;
    s.val = (sc[s.id] == s.c);
    return s;
}

F comp(F l, F r) { // first l, second r
    return r;
}

void build(int id, int l, int r, vector<int> &v, vector<int> &t) {
    tag[id] = F();
    if (l == r-1) {
        sc[id] = v[l];
        seg[id] = S(t[l], (t[l] == v[l]), id);
        return;
    }
    int mid = l + r >> 1;
    build(id * 2 + 1, l, mid, v, t);
    build(id * 2 + 2, mid, r, v, t);
    seg[id] = opr(seg[id * 2 + 1], seg[id * 2 + 2]);
    sc[id] = (sc[id * 2 + 1] == sc[id * 2 + 2] ? sc[id * 2 + 1] : -1);
}

void ins(int id, int l, int r, int L, int R, int op) {
    tag[id * 2 + 1] = comp(tag[id * 2 + 1], tag[id]);
    tag[id * 2 + 2] = comp(tag[id * 2 + 2], tag[id]);
    seg[id * 2 + 1] = M(tag[id * 2 + 1], seg[id * 2 + 1]);
    seg[id * 2 + 2] = M(tag[id * 2 + 2], seg[id * 2 + 2]);
    seg[id] = M(tag[id], seg[id]);
    tag[id] = F();
    // debug(l, r, id, tag[id].c, tag[3].c);
    if (L <= l && r <= R) {
        // debug(l, r, id);
        tag[id] = comp(tag[id], F(op));
        seg[id] = M(tag[id], seg[id]);
        // debug(id, seg[id].c, l, r, seg[id-1].c, tag[id-1].c, M(tag[id-1], seg[id-1]).c);
        return;
    }
    if (r <= L || l >= R) return;
    int mid = l + r >> 1;
    // debug(id);
    ins(id * 2 + 1, l, mid, L, R, op);
    ins(id * 2 + 2, mid, r, L, R, op);
    seg[id] = opr(seg[id * 2 + 1], seg[id * 2 + 2]);
    // debug(id, l, r, L, R, op, seg[id].val, sc[id], seg[id].c, tag[id].c);
}

void solve() {
    int n; cin >> n;
    vector<int> gene[3];
    for (int i = 0; i < 3; ++i) {
        string s; cin >> s;
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (s[j] == JOI[k]) gene[i].eb(k);
            }
        }
    }
    vector<vector<int>> G;
    G.eb(gene[0]);
    G.eb(gene[1]);
    G.eb(gene[2]);
    vector<int> t1 = cross(gene[0], gene[1]);
    vector<int> t2 = cross(gene[0], gene[2]);
    vector<int> t3 = cross(gene[1], gene[2]);
    G.eb(t1);
    G.eb(t2);
    G.eb(t3);
    G.eb(cross(t1, gene[2]));
    G.eb(cross(t2, gene[1]));
    G.eb(cross(t3, gene[0]));
    int q; cin >> q;
    string T; cin >> T;
    vector<int> gt;
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < 3; ++k) {
            if (T[i] == JOI[k]) gt.eb(k);
        }
    }
    vector<pair<pii, int>> qr;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        char c; cin >> c;
        int op = -1;
        for (int k = 0; k < 3; ++k) if (c == JOI[k]) op = k;
        qr.eb(pii(l, r), op);
    }

    vector<int> ans(q + 1);
    auto cal = [&](vector<int> &v) -> void {
        build(0, 0, n, v, gt);
        ans[0] |= M(tag[0], seg[0]).val;
        for (int i = 0; i < q; ++i){
            int l = qr[i].X.X, r = qr[i].X.Y, op = qr[i].Y;

            debug(tag[3].c);
            ins(0, 0, n, l, r, op);
            S val = M(tag[0], seg[0]);
            debug(val.c, val.val, val.id);
            ans[i+1] |= val.val;
        }
    };
    for (auto vec : G) {
        debug("ALIVE");
        for (auto it : vec) debug(it);
        cal(vec);
    }
    for (int i = 0; i <= q; ++i) {
        if (ans[i]) print("Yes");
        else print("No");
    }
}

signed main() {
    IOS();
    int t = 1; // cin >> t;
    for (int i=1;i<=t;++i) solve();
    return 0;
}

#else

#ifdef local 
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define X first
#define Y second

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "\e[1;93m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
    fprintf(stderr, "\e[1;96m"), \
    _P(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif

template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}

template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}

#endif

Compilation message (stderr)

Main.cpp: In function 'void build(int64_t, int64_t, int64_t, std::vector<long int>&, std::vector<long int>&)':
Main.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void ins(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:151:19: warning: unused variable 'it' [-Wunused-variable]
  151 |         for (auto it : vec) debug(it);
      |                   ^~

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