Submission #608845

#	Time	Username	Problem	Language	Result	Execution time	Memory
608845		DeMen100ns	Crossing (JOI21_crossing)	C++17	100 / 100	873 ms	20560 KiB

Main

/*
Author : DeMen100ns (a.k.a Vo Khac Trieu)
School : VNU-HCM High school for the Gifted
fuck you adhoc
*/

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const long long INF = numeric_limits<long long>::max() / 2;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

string cross(string a, string b){
    if (a.empty()) return b;

    string ans = "";
    for(int i = 0; i < a.size(); ++i){
        if (a[i] == b[i]) ans += a[i];
        else {
            int sum = (int)a[i] + b[i];
            if (sum == (int)'J' + 'O') ans += 'I';
            if (sum == (int)'I' + 'O') ans += 'J';
            if (sum == (int)'J' + 'I') ans += 'O';
        }
    }
    return ans;
}

vector <string> res;
bool f[20][4 * N];
bool d[4 * N];
char g[20][4 * N], sc[4 * N], lazy[4 * N];

void build(int id, int l, int r, string &s){
    for(int id2 = 0; id2 < res.size(); ++id2){
        f[id2][id] = true;
        for(int i = l; i <= r; ++i){
            f[id2][id] &= (s[i] == res[id2][i]);
        }
        bool ch = true;
        for(int i = l; i <= r; ++i){
            ch &= (res[id2][i] == res[id2][l]);
        }
        if (ch) g[id2][id] = res[id2][l];
        else g[id2][id] = 'z';
    }
    sc[id] = s[l];

    if (l == r) return;

    int mid = (l + r) >> 1;
    build(id << 1, l, mid, s);
    build(id << 1 | 1, mid + 1, r, s);
}

void down(int id){
    char ch = lazy[id];

    sc[id << 1] = sc[id << 1 | 1] = lazy[id << 1] = lazy[id << 1 | 1] = ch;
    d[id << 1] = d[id << 1 | 1] = true;
    for(int id2 = 0; id2 < res.size(); ++id2){
        f[id2][id << 1] = (g[id2][id << 1] == ch);
        f[id2][id << 1 | 1] = (g[id2][id << 1 | 1] == ch);
    }

    d[id] = false;
}

void upd(int id, int l, int r, int u, int v, char c){
    if (l > v || r < u) return;
    if (l >= u && r <= v){
        for(int id2 = 0; id2 < res.size(); ++id2){
            f[id2][id] = (g[id2][id] == c);
        }
        sc[id] = lazy[id] = c;
        d[id] = true;
        return;
    }
    if (d[id]) down(id);

    int mid = (l + r) >> 1;
    upd(id << 1, l, mid, u, v, c);
    upd(id << 1 | 1, mid + 1, r, u, v, c);

    for(int id2 = 0; id2 < res.size(); ++id2){
        f[id2][id] = (f[id2][id << 1] & f[id2][id << 1 | 1]);
    }
}

bool check(){
    bool g = false;
    for(int id2 = 0; id2 < res.size(); ++id2){
        g |= f[id2][1];
    }
    return g;
}

void solve()
{
    vector <string> v;

    int n; cin >> n;
    string S[3];
    for(int i = 0; i < 3; ++i) {
        cin >> S[i];
        v.push_back(S[i]);
    }

    //3 + 3 + 3 = 12

    sort(v.begin(), v.end());
    do{
        string ans = "";
        for(string s : v){
            ans = cross(ans, s);
            res.push_back(ans);
        }
    } while(next_permutation(v.begin(), v.end()));

    sort(res.begin(), res.end());
    res.resize(unique(res.begin(), res.end()) - res.begin());

    int q; cin >> q;
    string s; cin >> s;
    build(1, 0, n - 1, s);

    if (check()) cout << "Yes" << endl;
    else cout << "No" << endl;

    while (q--){
        int l, r; char c; cin >> l >> r >> c;
        --l; --r;

        upd(1, 0, n - 1, l, r, c);
        
        if (check()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    //i i j = i j = o
    //i j i = o i = j...
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("codeforces.inp","r",stdin);
    // freopen("codeforces.out","w",stdout);

    int t = 1; //cin >> t;
    while (t--)
    {
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'std::string cross(std::string, std::string)':
Main.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0; i < a.size(); ++i){
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'void build(int, int, int, std::string&)':
Main.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int id2 = 0; id2 < res.size(); ++id2){
      |                      ~~~~^~~~~~~~~~~~
Main.cpp: In function 'void down(int)':
Main.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int id2 = 0; id2 < res.size(); ++id2){
      |                      ~~~~^~~~~~~~~~~~
Main.cpp: In function 'void upd(int, int, int, int, int, char)':
Main.cpp:75:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int id2 = 0; id2 < res.size(); ++id2){
      |                          ~~~~^~~~~~~~~~~~
Main.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int id2 = 0; id2 < res.size(); ++id2){
      |                      ~~~~^~~~~~~~~~~~
Main.cpp: In function 'bool check()':
Main.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int id2 = 0; id2 < res.size(); ++id2){
      |                      ~~~~^~~~~~~~~~~~

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