Submission #423397

#	Time	Username	Problem	Language	Result	Execution time	Memory
423397		benedict0724	Crossing (JOI21_crossing)	C++17	100 / 100	969 ms	79656 KiB

Main

#include <iostream>

using namespace std;

int tree[800002][9], a[800002][9], b[800002][9], c[800002][9], lazy[800002];
int n, q;
string s[9], t;

string P(string S, string T)
{
    string ans;
    ans.resize(n);
    for(int i=0;i<n;i++)
    {
        if(S[i] == T[i]) ans[i] = S[i];
        else ans[i] = 'J' + 'O' + 'I' - S[i] - T[i];
    }
    return ans;
}

void propagate(int i, int l, int r)
{
    if(lazy[i] == 0) return;
    for(int j=0;j<9;j++)
    {
        if(lazy[i] == 1 && b[i][j] == 0 && c[i][j] == 0) tree[i][j] = 1;
        else if(lazy[i] == 2 && a[i][j] == 0 && c[i][j] == 0) tree[i][j] = 1;
        else if(lazy[i] == 3 && a[i][j] == 0 && b[i][j] == 0) tree[i][j] = 1;
        else tree[i][j] = 0;
    }

    if(l != r)
    {
        lazy[i*2] = lazy[i];
        lazy[i*2+1] = lazy[i];
    }
    lazy[i] = 0;
}

void init(int i, int l, int r)
{
    if(l == r)
    {
        for(int j=0;j<9;j++) if(s[j][l] == 'J') a[i][j] = 1;
        for(int j=0;j<9;j++) if(s[j][l] == 'O') b[i][j] = 1;
        for(int j=0;j<9;j++) if(s[j][l] == 'I') c[i][j] = 1;
        for(int j=0;j<9;j++) if(s[j][l] == t[l]) tree[i][j] = 1;
        return;
    }
    int m = (l + r)/2;
    init(i*2, l, m);
    init(i*2+1, m+1, r);
    for(int j=0;j<9;j++)
    {
        a[i][j] = a[i*2][j] | a[i*2+1][j];
        b[i][j] = b[i*2][j] | b[i*2+1][j];
        c[i][j] = c[i*2][j] | c[i*2+1][j];
        tree[i][j] = tree[i*2][j] & tree[i*2+1][j];
    }
}

void update(int i, int l, int r, int s, int e, int v)
{
    propagate(i, l, r);
    if(e < l || r < s) return;
    if(s <= l && r <= e)
    {
        lazy[i] = v;
        propagate(i, l, r);
        return;
    }
    int m = (l + r)/2;
    update(i*2, l, m, s, e, v);
    update(i*2+1, m+1, r, s, e, v);
    for(int j=0;j<9;j++) tree[i][j] = tree[i*2][j] & tree[i*2+1][j];
}

int query()
{
    for(int i=0;i<9;i++)
    {
        if(tree[1][i]) return 1;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    cin >> s[0] >> s[1] >> s[2];
    s[3] = P(s[0], s[1]);
    s[4] = P(s[0], s[2]);
    s[5] = P(s[1], s[2]);
    s[6] = P(s[0], s[5]);
    s[7] = P(s[1], s[4]);
    s[8] = P(s[2], s[3]);
    cin >> q;
    cin >> t;
    init(1, 0, n-1);
    cout << (query() ? "Yes\n" : "No\n");
    for(int i=1;i<=q;i++)
    {
        int l, r, ch; char c;
        cin >> l >> r >> c;
        if(c == 'J') ch = 1;
        if(c == 'O') ch = 2;
        if(c == 'I') ch = 3;
        update(1, 0, n-1, l-1, r-1, ch);
        cout << (query() ? "Yes\n" : "No\n");
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:109:15: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |         update(1, 0, n-1, l-1, r-1, ch);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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