Submission #866687

#	Time	Username	Problem	Language	Result	Execution time	Memory
866687		vjudge1	Crossing (JOI21_crossing)	C++17	26 / 100	513 ms	15124 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int const MAXN=2e6, K=(1<<18);

int n, q;
string a, b, c, p;
bool tree[2*K-1];
char lazy[2*K-1];
int jprefix[MAXN], oprefix[MAXN], iprefix[MAXN];

bool good(int l, int r, char c)
{
    r=min(r, n)-1;
    if (l>r)
        return true;
    int total;
    if (c=='J')
    {
        total=jprefix[r];
        if (l!=0)
            total=total-jprefix[l-1];
    }
    if (c=='O')
    {
        total=oprefix[r];
        if (l!=0)
            total=total-oprefix[l-1];
    }
    if (c=='I')
    {
        total=iprefix[r];
        if (l!=0)
            total=total-iprefix[l-1];
    }

    return total==r-l+1;
}

void propagate(int x, int l, int r)
{
    if (lazy[x]=='#')
        return;
    if (r-l==1)
    {
        lazy[x]='#';
        return;
    }
    tree[2*x+1]=good(l, (l+r)/2, lazy[x]);
    lazy[2*x+1]=lazy[x];
    tree[2*x+2]=good((l+r)/2, r, lazy[x]);
    lazy[2*x+2]=lazy[x];
    lazy[x]='#';

    return;
}

void update(int x, int l, int r, char c, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return;
    if (l>=lt && r<=rt)
    {
        tree[x]=good(l, r, c);
        lazy[x]=c;
        return;
    }
    propagate(x, l, r);
    update(2*x+1, l, (l+r)/2, c, lt, rt);
    update(2*x+2, (l+r)/2, r, c, lt, rt);
    if (r-l==1)
    {
        if (l>=n)
            tree[x]=true;
        else
            tree[x]=(a[l]==c);
    }
    else
        tree[x]=(tree[2*x+1]&tree[2*x+2]);
    //cout << "l r c " << l << " " << r << " " << c << " " << tree[x] << '\n';

    return;
}

int main()
{
    cin >> n >> a >> b >> c;
    cin >> q >> p;
    for (int i=0; i<2*K-1; i++)
    {
        tree[i]=true;
        lazy[i]='#';
    }
    jprefix[0]=0;
    oprefix[0]=0;
    iprefix[0]=0;
    if (a[0]=='J')
        jprefix[0]=1;
    if (a[0]=='O')
        oprefix[0]=1;
    if (a[0]=='I')
        iprefix[0]=1;
    for (int i=1; i<n; i++)
    {
        jprefix[i]=jprefix[i-1];
        oprefix[i]=oprefix[i-1];
        iprefix[i]=iprefix[i-1];
        if (a[i]=='J')
            jprefix[i]=jprefix[i]+1;
        if (a[i]=='O')
            oprefix[i]=oprefix[i]+1;
        if (a[i]=='I')
            iprefix[i]=iprefix[i]+1;
    }
    for (int i=0; i<n; i++)
        update(0, 0, K, p[i], i, i+1);
    //cout << "treee" << '\n';
    //for (int i=0; i<2*K-1; i++)
      //  cout << tree[i] << " ";
    //cout << '\n';
    if (tree[0])
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';
    while (q--)
    {
        int l, r;
        char c;
        cin >> l >> r >> c;
        l=l-1;
        update(0, 0, K, c, l, r);
        if (tree[0])
            cout << "Yes" << '\n';
        else
            cout << "No" << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool good(int, int, char)':
Main.cpp:37:23: warning: 'total' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     return total==r-l+1;
      |                       ^

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