Submission #423384

#	Time	Username	Problem	Language	Result	Execution time	Memory
423384		benedict0724	Crossing (JOI21_crossing)	C++17	26 / 100	333 ms	12172 KiB

Main

#include <iostream>

using namespace std;

int tree[800002], a[800002], b[800002], c[800002], lazy[800002];
int n, q;
string s1, s2, s3, t;

void propagate(int i, int l, int r)
{
    if(lazy[i] == 0) return;
    if(lazy[i] == 1 && b[i] == 0 && c[i] == 0) tree[i] = 1;
    else if(lazy[i] == 2 && a[i] == 0 && c[i] == 0) tree[i] = 1;
    else if(lazy[i] == 3 && a[i] == 0 && b[i] == 0) tree[i] = 1;
    else tree[i] = 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)
    {
        if(s1[l] == 'J') a[i] = 1;
        if(s1[l] == 'O') b[i] = 1;
        if(s1[l] == 'I') c[i] = 1;
        if(s1[l] == t[l]) tree[i] = 1;
        return;
    }
    int m = (l + r)/2;
    init(i*2, l, m);
    init(i*2+1, m+1, r);
    a[i] = a[i*2] | a[i*2+1];
    b[i] = b[i*2] | b[i*2+1];
    c[i] = c[i*2] | c[i*2+1];
    tree[i] = tree[i*2] & tree[i*2+1];
}

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);
    tree[i] = tree[i*2] & tree[i*2+1];
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    cin >> s1 >> s2 >> s3;
    cin >> q;
    cin >> t;
    init(1, 0, n-1);
    cout << (tree[1] ? "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 << (tree[1] ? "Yes\n" : "No\n");
    }
}

Compilation message (stderr)

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

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