Submission #1117372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117372		Sharky	Crossing (JOI21_crossing)	C++17	100 / 100	1489 ms	27468 KiB

Main

#include "bits/stdc++.h"
using namespace std;

int n;
string T = "JOI";
string S;

string cross(string& a, string& b) {
    string res;
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i]) res += a[i];
        else for (char& c : T) if (a[i] != c && b[i] != c) res += c;
    }
    return res;
}

struct Node {
    char rng = '?';
    bool same = false;
} dummy;

struct SegTree {
    int size = 1;
    string tar;
    vector<Node> seg;
    vector<char> lazy;
    void init(int n, string _tar) {
        while (size < n) size *= 2;
        tar = _tar;
        seg.assign(2 * size + 10, dummy);
        lazy.assign(2 * size + 10, '?');
    }
    void push(int id) {
        if (lazy[id] != '?') {
            seg[id].same = (seg[id].rng == lazy[id]);
            if (id < size) for (int i = 0; i < 2; i++) lazy[id * 2 + i] = lazy[id];
        }
        lazy[id] = '?';
    }
    void pull(int id) {
        if (!seg[id * 2].same || !seg[id * 2 + 1].same) seg[id].same = false;
        else seg[id].same = true;
    }
    void build(int l, int r, int id) {
        if (l == r) {
            seg[id].rng = tar[l];
            seg[id].same = (tar[l] == S[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, id * 2);
        build(mid + 1, r, id * 2 + 1);
        if (seg[id * 2].rng == seg[id * 2 + 1].rng) seg[id].rng = seg[id * 2].rng;
        else seg[id].rng = '?';
        pull(id);
    }
    void update(int ql, int qr, char c, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[id] = c;
            push(id);
            return;
        }
        int mid = (l + r) >> 1;
        update(ql, qr, c, l, mid, id * 2);
        update(ql, qr, c, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    bool query(int ql, int qr, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return true;
        if (ql <= l && r <= qr) return seg[id].same;
        int mid = (l + r) >> 1;
        bool L = query(ql, qr, l, mid, id * 2);
        bool R = query(ql, qr, mid + 1, r, id * 2 + 1);
        if (!L || !R) return false;
        return true;
    }
} ST[9];

struct Query {
    int l, r;
    char c;
};

int main() {
    string a, b, c;
    cin >> n >> a >> b >> c;
    set<string> proc;
    queue<string> q;
    q.push(a); q.push(b); q.push(c);
    while (!q.empty()) {
        string s = q.front();
        q.pop();
        for (auto t : proc) {
            string res = cross(s, t);
            if (!proc.count(res)) q.push(res);
        }
        proc.insert(s);
    }
    vector<string> str;
    for (auto x : proc) str.push_back(x);
    int queries;
    cin >> queries;
    vector<Query> Q(queries);
    vector<bool> ans(queries, false);
    cin >> S;
    S = '.' + S;
    for (int i = 0; i < queries; i++) cin >> Q[i].l >> Q[i].r >> Q[i].c;
    for (int i = 0; i < min((int) str.size(), 9); i++) {
        str[i] = '.' + str[i];
        ST[i].init(n + 1, str[i]);
        ST[i].build(1, n, 1);
    }
    bool init = false;
    for (int i = 0; i < min((int) str.size(), 9); i++) {
        if (ST[i].query(1, n, 1, n, 1)) {
            init = true;
            break;
        }
    }
    cout << (init ? "Yes\n" : "No\n");
    for (int i = 0; i < queries; i++) {
        auto [l, r, ch] = Q[i];
        for (int j = 0; j < min((int) str.size(), 9); j++) {
            ST[j].update(l, r, ch, 1, n, 1);
            if (!ans[i] && ST[j].query(1, n, 1, n, 1)) ans[i] = true;
        }
        cout << (ans[i] ? "Yes\n" : "No\n");
    }
}

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