Submission #864322

#	Time	Username	Problem	Language	Result	Execution time	Memory
864322		vjudge1	Crossing (JOI21_crossing)	C++17	100 / 100	2650 ms	76636 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

int n;
string t;

struct SegmentTree {

    string s;
    vector<int> sgt, lz;
    vector<char> let, slet;

    void build(int k = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            let[k] = t[l];
            if (t[l] == s[l]) sgt[k] = 1;
            else sgt[k] = 0;
            slet[k] = s[l];
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
        sgt[k] = sgt[k * 2] * sgt[k * 2 + 1];
        let[k] = 'z';
        if (let[k * 2] == let[k * 2 + 1]) let[k] = let[k * 2];
        slet[k] = 'z';
        if (slet[k * 2] == slet[k * 2 + 1]) slet[k] = slet[k * 2];
    }

    void init(string a) {
        s = a;
        sgt.resize(4 * n);
        let.resize(4 * n);
        slet.resize(4 * n);
        lz.resize(4 * n);
        build();
    }

    void push(int k, int l, int r) {
        if (l == r) return;
        if (lz[k]) {
            if (l != r) lz[k * 2] = lz[k * 2 + 1] = 1;
            let[k * 2] = let[k * 2 + 1] = let[k];
            if (slet[k * 2] == let[k * 2]) sgt[k * 2] = 1;
            else sgt[k * 2] = 0;
            if (slet[k * 2 + 1] == let[k * 2 + 1]) sgt[k * 2 + 1] = 1;
            else sgt[k * 2 + 1] = 0;
            sgt[k] = sgt[k * 2] * sgt[k * 2 + 1];
        }
        lz[k] = 0;
    }

    void update(int k, int l, int r, int i, int j, char v) {
        push(k, l, r);
        if (l > j || r < i) return;
        if (i <= l && r <= j) {
            if (slet[k] == v) sgt[k] = 1;
            else sgt[k] = 0;
            let[k] = v;
            lz[k] = 1;
            // cout << s << " " << l << " - " << r << " " << sgt[k] << " " << let[k] << endl;
            return;
        }
        int m = (l + r) / 2;
        update(k * 2, l, m, i, j, v);
        update(k * 2 + 1, m + 1, r, i, j, v);
        sgt[k] = sgt[k * 2] * sgt[k * 2 + 1];
        let[k] = 'z';
        if (let[k * 2] == let[k * 2 + 1]) let[k] = let[k * 2];
        // cout << s << " " << l << " - " << r << " " << sgt[k] << " " << let[k] << endl;
    }
};


string merge(string a, string b) {
    string c = "";
    for (int i = 0; i < a.size(); i++) {
        if (a[i] == b[i]) c += a[i];
        else {
            set<char> f;
            f.insert(a[i]);
            f.insert(b[i]);
            if (!f.count('J')) c += "J";
            if (!f.count('O')) c += "O";
            if (!f.count('I')) c += "I";
        }
    }
    return c;
}

vector<SegmentTree> v(9);

int cnt;

bool pos() {
    int flag = 0;
    for (int i = 0; i < cnt; i++) flag = max(flag, v[i].sgt[1]);
    return flag;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s[3];
    for (int i = 0; i < 3; i++) cin >> s[i];
    set<string> all;
    all.insert(s[0]);
    all.insert(s[1]);
    all.insert(s[2]);
    all.insert(merge(s[0], s[1]));
    all.insert(merge(s[0], s[2]));
    all.insert(merge(s[1], s[2]));
    all.insert(merge(s[0], merge(s[1], s[2])));
    all.insert(merge(s[1], merge(s[0], s[2])));
    all.insert(merge(s[2], merge(s[0], s[1])));
    int q;
    cin >> q;
    cin >> t;
    for (auto x : all) {
        v[cnt++].init(x);
    }
    cout << (pos() ? "Yes" : "No") << endl;
    while (q--) {
        int l, r;
        char x;
        cin >> l >> r >> x;
        l--;
        r--;
        for (int i = 0; i < cnt; i++) v[i].update(1, 0, n - 1, l, r, x);
        cout << (pos() ? "Yes" : "No") << endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::string merge(std::string, std::string)':
Main.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

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