oj.uz

답안 #864294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
864294 2023-10-22T10:42:28 Z vjudge1 Crossing (JOI21_crossing) C++17
0 / 100
 80 ms 2524 KB 
#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] = 'y';
        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);
        push(k * 2, l, m);
        push(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];
        // 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

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

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 956 KB Output is correct
2 Correct 80 ms 2384 KB Output is correct
3 Correct 79 ms 2388 KB Output is correct
4 Incorrect 73 ms 2524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 956 KB Output is correct
2 Correct 80 ms 2384 KB Output is correct
3 Correct 79 ms 2388 KB Output is correct
4 Incorrect 73 ms 2524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 956 KB Output is correct
2 Correct 80 ms 2384 KB Output is correct
3 Correct 79 ms 2388 KB Output is correct
4 Incorrect 73 ms 2524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 956 KB Output is correct
2 Correct 80 ms 2384 KB Output is correct
3 Correct 79 ms 2388 KB Output is correct
4 Incorrect 73 ms 2524 KB Output isn't correct
5 Halted 0 ms 0 KB -