Submission #891382

#	Time	Username	Problem	Language	Result	Execution time	Memory
891382		coldEr66	Crossing (JOI21_crossing)	C++14	100 / 100	969 ms	54536 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;

struct node {
    int sc, tc, val, tag;
} seg[maxn * 4];

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

void push(int id) {
    if (seg[id].tag == -1) return;
    seg[id * 2 + 1].tag = seg[id].tag;
    seg[id * 2 + 2].tag = seg[id].tag;
    seg[id].tag = -1;
}

void ins(int id, int l, int r, int L, int R, int op) {
    if (L <= l && R >= r) {
        seg[id].tag = op;
        seg[id].tc = op;
        seg[id].val = (seg[id].tc == seg[id].sc);
        return;
    }
    if (r <= L || l >= R) return;
    int mid = l + r >> 1;
    push(id);
    ins(id * 2 + 1, l, mid, L, R, op);
    ins(id * 2 + 2, mid, r, L, R, op);

    int lc = (seg[id * 2 + 1].tag == -1 ? seg[id * 2 + 1].tc : seg[id * 2 + 1].tag);
    int rc = (seg[id * 2 + 2].tag == -1 ? seg[id * 2 + 2].tc : seg[id * 2 + 2].tag);
    int lval = (seg[id * 2 + 1].tag == -1 ? seg[id * 2 + 1].val : (seg[id * 2 + 1].tag == seg[id * 2 + 1].sc));
    int rval = (seg[id * 2 + 2].tag == -1 ? seg[id * 2 + 2].val : (seg[id * 2 + 2].tag == seg[id * 2 + 2].sc));
    seg[id].tc = (lc == rc ? lc : -1);
    seg[id].val = lval & rval;
}

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] |= 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;

            ins(0, 0, n, l, r, op);
            ans[i+1] |= seg[0].val;
        }
    };
    for (auto vec : G) {
        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:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     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:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~

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