Submission #580462

#	Time	Username	Problem	Language	Result	Execution time	Memory
580462		colossal_pepe	Crossing (JOI21_crossing)	C++17	100 / 100	570 ms	117140 KiB

Main

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
using namespace std;

struct Node {
    int cnt_s[9][3], cnt_t[3];
    bool match[9];
    int lazy;
    Node() {
        memset(cnt_s, 0, sizeof(cnt_s));
        memset(cnt_t, 0, sizeof(cnt_t));
        lazy = -1;
    }
};

int n, q;
set<string> dict;
vector<string> all, now(3);
string t;
vector<Node> sgt;

int id(char c) {
    if (c == 'J') return 0;
    else if (c == 'O') return 1;
    else return 2;
}

void init(int u, int l, int r) {
    if (l == r) {
        sgt[u].cnt_t[id(t[l])]++;
        for (int i = 0; i < 9; i++) {
            sgt[u].cnt_s[i][id(all[i][l])]++;
            sgt[u].match[i] = (all[i][l] == t[l]);
        }
    } else {
        int mid = (l + r) / 2;
        init(2 * u, l, mid);
        init(2 * u + 1, mid + 1, r);
        for (int i = 0; i < 3; i++) {
            sgt[u].cnt_t[i] = sgt[2 * u].cnt_t[i] + sgt[2 * u + 1].cnt_t[i];
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 3; j++) {
                sgt[u].cnt_s[i][j] = sgt[2 * u].cnt_s[i][j] + sgt[2 * u + 1].cnt_s[i][j];
            }
            sgt[u].match[i] = (sgt[2 * u].match[i] & sgt[2 * u + 1].match[i]);
        }
    }
}

void update(int u, int l, int r, int L, int R, int x) {
    if (r < L or R < l) return;
    else if (L <= l and r <= R) {
        memset(sgt[u].cnt_t, 0, sizeof(sgt[u].cnt_t));
        sgt[u].cnt_t[x] = r - l + 1;
        sgt[u].lazy = x;
        for (int i = 0; i < 9; i++) {
            sgt[u].match[i] = (sgt[u].cnt_s[i][x] == sgt[u].cnt_t[x]);
        }
    } else {
        int mid = (l + r) / 2;
        if (sgt[u].lazy != -1) {
            memset(sgt[2 * u].cnt_t, 0, sizeof(sgt[2 * u].cnt_t));
            memset(sgt[2 * u + 1].cnt_t, 0, sizeof(sgt[2 * u + 1].cnt_t));
            sgt[2 * u].cnt_t[sgt[u].lazy] = mid - l + 1;
            sgt[2 * u + 1].cnt_t[sgt[u].lazy] = r - mid;
            for (int i = 0; i < 9; i++) {
                sgt[2 * u].match[i] = (sgt[2 * u].cnt_s[i][sgt[u].lazy] == sgt[2 * u].cnt_t[sgt[u].lazy]);
                sgt[2 * u + 1].match[i] = (sgt[2 * u + 1].cnt_s[i][sgt[u].lazy] == sgt[2 * u + 1].cnt_t[sgt[u].lazy]);
            }
            sgt[2 * u].lazy = sgt[2 * u + 1].lazy = sgt[u].lazy;
            sgt[u].lazy = -1;
        }
        update(2 * u, l, mid, L, R, x);
        update(2 * u + 1, mid + 1, r, L, R, x);
        for (int i = 0; i < 3; i++) {
            sgt[u].cnt_t[i] = sgt[2 * u].cnt_t[i] + sgt[2 * u + 1].cnt_t[i];
        }
        for (int i = 0; i < 9; i++) {
            sgt[u].match[i] = (sgt[2 * u].match[i] & sgt[2 * u + 1].match[i]);
        }
    }
}

char crossChar(char c1, char c2) {
    if (c1 == c2) return c1;
    if (c1 != 'J' and c2 != 'J') return 'J';
    else if (c1 != 'O' and c2 != 'O') return 'O';
    else return 'I';
}
 
string crossStr(string s1, string s2) {
    string ret;
    for (int i = 0; i < s1.size(); i++) {
        ret += crossChar(s1[i], s2[i]);
    }
    return ret;
}

void generate() {
    while (not now.empty()) {
        string s = now.back();
        now.pop_back();
        if (dict.find(s) != dict.end()) continue;
        dict.insert(s);
        all.push_back(s);
        for (string t : all) {
            now.push_back(crossStr(s, t));
        }
    }
    while (all.size() < 9) {
        all.push_back(all.back());
    }
}

bool check() {
    for (int i = 0; i < 9; i++) {
        if (sgt[1].match[i]) return 1;
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> now[0] >> now[1] >> now[2];
    generate();
    cin >> q >> t;
    sgt.resize(4 * n, Node());
    init(1, 0, n - 1);
    cout << (check() ? "Yes" : "No") << '\n';
    while (q--) {
        int l, r;
        char c;
        cin >> l >> r >> c;
        update(1, 0, n - 1, l - 1, r - 1, id(c));
        cout << (check() ? "Yes" : "No") << '\n';
    }
    return 0;
}

Compilation message (stderr)

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

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