oj.uz

Submission #866687

# Submission time Handle Problem Language Result Execution time Memory
866687 2023-10-26T17:53:29 Z vjudge1 Crossing (JOI21_crossing) C++17
26 / 100
 513 ms 15124 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 7520 KB Output is correct
2 Correct 341 ms 7688 KB Output is correct
3 Correct 344 ms 7428 KB Output is correct
4 Correct 325 ms 7508 KB Output is correct
5 Correct 320 ms 7520 KB Output is correct
6 Correct 314 ms 7504 KB Output is correct
7 Correct 339 ms 7448 KB Output is correct
8 Correct 334 ms 7508 KB Output is correct
9 Correct 336 ms 7664 KB Output is correct
10 Correct 336 ms 7504 KB Output is correct
11 Correct 339 ms 7548 KB Output is correct
12 Correct 334 ms 7508 KB Output is correct
13 Correct 341 ms 7592 KB Output is correct
14 Correct 334 ms 7632 KB Output is correct
15 Correct 337 ms 7600 KB Output is correct
16 Correct 351 ms 7508 KB Output is correct
17 Correct 336 ms 7508 KB Output is correct
18 Correct 342 ms 7504 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 7520 KB Output is correct
2 Correct 341 ms 7688 KB Output is correct
3 Correct 344 ms 7428 KB Output is correct
4 Correct 325 ms 7508 KB Output is correct
5 Correct 320 ms 7520 KB Output is correct
6 Correct 314 ms 7504 KB Output is correct
7 Correct 339 ms 7448 KB Output is correct
8 Correct 334 ms 7508 KB Output is correct
9 Correct 336 ms 7664 KB Output is correct
10 Correct 336 ms 7504 KB Output is correct
11 Correct 339 ms 7548 KB Output is correct
12 Correct 334 ms 7508 KB Output is correct
13 Correct 341 ms 7592 KB Output is correct
14 Correct 334 ms 7632 KB Output is correct
15 Correct 337 ms 7600 KB Output is correct
16 Correct 351 ms 7508 KB Output is correct
17 Correct 336 ms 7508 KB Output is correct
18 Correct 342 ms 7504 KB Output is correct
19 Correct 485 ms 14996 KB Output is correct
20 Correct 501 ms 14832 KB Output is correct
21 Correct 406 ms 14740 KB Output is correct
22 Correct 409 ms 14484 KB Output is correct
23 Correct 368 ms 8532 KB Output is correct
24 Correct 373 ms 8548 KB Output is correct
25 Correct 447 ms 14904 KB Output is correct
26 Correct 470 ms 14996 KB Output is correct
27 Correct 456 ms 14852 KB Output is correct
28 Correct 468 ms 14880 KB Output is correct
29 Correct 465 ms 14816 KB Output is correct
30 Correct 373 ms 8536 KB Output is correct
31 Correct 463 ms 15096 KB Output is correct
32 Correct 445 ms 14644 KB Output is correct
33 Correct 370 ms 8456 KB Output is correct
34 Correct 462 ms 14996 KB Output is correct
35 Correct 401 ms 14128 KB Output is correct
36 Correct 369 ms 8580 KB Output is correct
37 Correct 371 ms 8596 KB Output is correct
38 Correct 478 ms 15016 KB Output is correct
39 Correct 415 ms 14996 KB Output is correct
40 Correct 428 ms 12228 KB Output is correct
41 Correct 513 ms 15124 KB Output is correct
42 Correct 380 ms 14384 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 7520 KB Output is correct
2 Correct 341 ms 7688 KB Output is correct
3 Correct 344 ms 7428 KB Output is correct
4 Correct 325 ms 7508 KB Output is correct
5 Correct 320 ms 7520 KB Output is correct
6 Correct 314 ms 7504 KB Output is correct
7 Correct 339 ms 7448 KB Output is correct
8 Correct 334 ms 7508 KB Output is correct
9 Correct 336 ms 7664 KB Output is correct
10 Correct 336 ms 7504 KB Output is correct
11 Correct 339 ms 7548 KB Output is correct
12 Correct 334 ms 7508 KB Output is correct
13 Correct 341 ms 7592 KB Output is correct
14 Correct 334 ms 7632 KB Output is correct
15 Correct 337 ms 7600 KB Output is correct
16 Correct 351 ms 7508 KB Output is correct
17 Correct 336 ms 7508 KB Output is correct
18 Correct 342 ms 7504 KB Output is correct
19 Correct 351 ms 7540 KB Output is correct
20 Correct 345 ms 7508 KB Output is correct
21 Incorrect 339 ms 7960 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 7520 KB Output is correct
2 Correct 341 ms 7688 KB Output is correct
3 Correct 344 ms 7428 KB Output is correct
4 Correct 325 ms 7508 KB Output is correct
5 Correct 320 ms 7520 KB Output is correct
6 Correct 314 ms 7504 KB Output is correct
7 Correct 339 ms 7448 KB Output is correct
8 Correct 334 ms 7508 KB Output is correct
9 Correct 336 ms 7664 KB Output is correct
10 Correct 336 ms 7504 KB Output is correct
11 Correct 339 ms 7548 KB Output is correct
12 Correct 334 ms 7508 KB Output is correct
13 Correct 341 ms 7592 KB Output is correct
14 Correct 334 ms 7632 KB Output is correct
15 Correct 337 ms 7600 KB Output is correct
16 Correct 351 ms 7508 KB Output is correct
17 Correct 336 ms 7508 KB Output is correct
18 Correct 342 ms 7504 KB Output is correct
19 Correct 485 ms 14996 KB Output is correct
20 Correct 501 ms 14832 KB Output is correct
21 Correct 406 ms 14740 KB Output is correct
22 Correct 409 ms 14484 KB Output is correct
23 Correct 368 ms 8532 KB Output is correct
24 Correct 373 ms 8548 KB Output is correct
25 Correct 447 ms 14904 KB Output is correct
26 Correct 470 ms 14996 KB Output is correct
27 Correct 456 ms 14852 KB Output is correct
28 Correct 468 ms 14880 KB Output is correct
29 Correct 465 ms 14816 KB Output is correct
30 Correct 373 ms 8536 KB Output is correct
31 Correct 463 ms 15096 KB Output is correct
32 Correct 445 ms 14644 KB Output is correct
33 Correct 370 ms 8456 KB Output is correct
34 Correct 462 ms 14996 KB Output is correct
35 Correct 401 ms 14128 KB Output is correct
36 Correct 369 ms 8580 KB Output is correct
37 Correct 371 ms 8596 KB Output is correct
38 Correct 478 ms 15016 KB Output is correct
39 Correct 415 ms 14996 KB Output is correct
40 Correct 428 ms 12228 KB Output is correct
41 Correct 513 ms 15124 KB Output is correct
42 Correct 380 ms 14384 KB Output is correct
43 Correct 351 ms 7540 KB Output is correct
44 Correct 345 ms 7508 KB Output is correct
45 Incorrect 339 ms 7960 KB Output isn't correct
46 Halted 0 ms 0 KB -