oj.uz

Submission #916175

# Submission time Handle Problem Language Result Execution time Memory
916175 2024-01-25T12:26:52 Z 12345678 Crossing (JOI21_crossing) C++17
100 / 100
 262 ms 33516 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

mt19937 rng(time(NULL));

const int nx=2e5+5, mod=1e9+7, base=(rng()%mod+mod)%mod;
ll n, mp[100], q, k[10], l, r;
char ch;
vector<ll> d[10], p(nx), qsp(nx);
string s[3], t;

struct segtree
{
    ll d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        if (lz[i]==-1) return;
        if (l==r) return d[i]=(((qsp[r]-qsp[l-1])*lz[i])%mod+mod)%mod, lz[i]=-1, void();
        d[i]=(((qsp[r]-qsp[l-1])*lz[i])%mod+mod)%mod;
        lz[2*i]=lz[i];
        lz[2*i+1]=lz[i];
        lz[i]=-1;
    }
    void build(int l, int r, int i)
    {
        lz[i]=-1;
        if (l==r) return lz[i]=mp[(int)t[l-1]], pushlz(l, r, i);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=(d[2*i]+d[2*i+1])%mod;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=(d[2*i]+d[2*i+1])%mod;
    }
    bool check()
    {
        for (int i=0; i<9; i++) if (k[i]==d[1]) return 1;
        return 0;
    }
} st;

ll getval(vector<ll> &str)
{
    ll res=0;
    for (int i=1; i<=n; i++) res=(res+p[i]*str[i])%mod;
    return res;
}

vector<ll> cross(vector<ll> &lhs, vector<ll> &rhs)
{
    vector<ll> res(nx);
    for (int i=1; i<=n; i++) res[i]=((lhs[i]+rhs[i])*2)%3;
    return res;
}


int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    for (int i=0; i<9; i++) d[i].resize(nx);
    mp['J']=0; mp['O']=1; mp['I']=2;
    p[1]=qsp[1]=1;
    for (int i=2; i<nx; i++) p[i]=(p[i-1]*base)%mod, qsp[i]=(qsp[i-1]+p[i])%mod;
    cin>>n>>s[0]>>s[1]>>s[2];
    for (int i=0; i<3; i++) for (int j=1; j<=n; j++) d[i][j]=mp[(int)s[i][j-1]];
    d[3]=cross(d[0], d[1]);
    d[4]=cross(d[0], d[2]);
    d[5]=cross(d[1], d[2]);
    d[6]=cross(d[3], d[2]);
    d[7]=cross(d[4], d[1]);
    d[8]=cross(d[5], d[0]);
    for (int i=0; i<9; i++) k[i]=getval(d[i]);
    cin>>q>>t;
    st.build(1, n, 1);
    cout<<(st.check()?"Yes":"No")<<'\n';
    while (q--)
    {
        cin>>l>>r>>ch;
        st.update(1, n, 1, l, r, mp[(int)ch]);
        //cout<<"here "<<st.d[1]<<'\n';
        cout<<(st.check()?"Yes":"No")<<'\n';
    }
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21656 KB Output is correct
2 Correct 71 ms 21784 KB Output is correct
3 Correct 69 ms 21676 KB Output is correct
4 Correct 62 ms 21760 KB Output is correct
5 Correct 62 ms 21732 KB Output is correct
6 Correct 63 ms 21660 KB Output is correct
7 Correct 65 ms 21676 KB Output is correct
8 Correct 65 ms 21792 KB Output is correct
9 Correct 65 ms 21780 KB Output is correct
10 Correct 79 ms 21776 KB Output is correct
11 Correct 67 ms 21820 KB Output is correct
12 Correct 69 ms 21832 KB Output is correct
13 Correct 65 ms 21664 KB Output is correct
14 Correct 82 ms 21816 KB Output is correct
15 Correct 66 ms 21816 KB Output is correct
16 Correct 71 ms 21644 KB Output is correct
17 Correct 68 ms 21872 KB Output is correct
18 Correct 67 ms 21664 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21656 KB Output is correct
2 Correct 71 ms 21784 KB Output is correct
3 Correct 69 ms 21676 KB Output is correct
4 Correct 62 ms 21760 KB Output is correct
5 Correct 62 ms 21732 KB Output is correct
6 Correct 63 ms 21660 KB Output is correct
7 Correct 65 ms 21676 KB Output is correct
8 Correct 65 ms 21792 KB Output is correct
9 Correct 65 ms 21780 KB Output is correct
10 Correct 79 ms 21776 KB Output is correct
11 Correct 67 ms 21820 KB Output is correct
12 Correct 69 ms 21832 KB Output is correct
13 Correct 65 ms 21664 KB Output is correct
14 Correct 82 ms 21816 KB Output is correct
15 Correct 66 ms 21816 KB Output is correct
16 Correct 71 ms 21644 KB Output is correct
17 Correct 68 ms 21872 KB Output is correct
18 Correct 67 ms 21664 KB Output is correct
19 Correct 183 ms 33400 KB Output is correct
20 Correct 185 ms 33088 KB Output is correct
21 Correct 129 ms 33056 KB Output is correct
22 Correct 122 ms 32848 KB Output is correct
23 Correct 96 ms 26796 KB Output is correct
24 Correct 95 ms 26772 KB Output is correct
25 Correct 131 ms 33388 KB Output is correct
26 Correct 137 ms 33372 KB Output is correct
27 Correct 149 ms 33232 KB Output is correct
28 Correct 168 ms 33372 KB Output is correct
29 Correct 144 ms 33224 KB Output is correct
30 Correct 101 ms 26888 KB Output is correct
31 Correct 146 ms 33348 KB Output is correct
32 Correct 166 ms 33036 KB Output is correct
33 Correct 102 ms 26972 KB Output is correct
34 Correct 143 ms 33176 KB Output is correct
35 Correct 113 ms 32628 KB Output is correct
36 Correct 98 ms 26892 KB Output is correct
37 Correct 94 ms 26900 KB Output is correct
38 Correct 165 ms 33096 KB Output is correct
39 Correct 108 ms 33348 KB Output is correct
40 Correct 131 ms 28516 KB Output is correct
41 Correct 262 ms 33376 KB Output is correct
42 Correct 59 ms 32848 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21656 KB Output is correct
2 Correct 71 ms 21784 KB Output is correct
3 Correct 69 ms 21676 KB Output is correct
4 Correct 62 ms 21760 KB Output is correct
5 Correct 62 ms 21732 KB Output is correct
6 Correct 63 ms 21660 KB Output is correct
7 Correct 65 ms 21676 KB Output is correct
8 Correct 65 ms 21792 KB Output is correct
9 Correct 65 ms 21780 KB Output is correct
10 Correct 79 ms 21776 KB Output is correct
11 Correct 67 ms 21820 KB Output is correct
12 Correct 69 ms 21832 KB Output is correct
13 Correct 65 ms 21664 KB Output is correct
14 Correct 82 ms 21816 KB Output is correct
15 Correct 66 ms 21816 KB Output is correct
16 Correct 71 ms 21644 KB Output is correct
17 Correct 68 ms 21872 KB Output is correct
18 Correct 67 ms 21664 KB Output is correct
19 Correct 81 ms 21940 KB Output is correct
20 Correct 75 ms 21752 KB Output is correct
21 Correct 64 ms 21676 KB Output is correct
22 Correct 59 ms 21484 KB Output is correct
23 Correct 70 ms 21660 KB Output is correct
24 Correct 64 ms 21660 KB Output is correct
25 Correct 65 ms 21664 KB Output is correct
26 Correct 62 ms 21692 KB Output is correct
27 Correct 64 ms 21780 KB Output is correct
28 Correct 58 ms 21464 KB Output is correct
29 Correct 66 ms 21740 KB Output is correct
30 Correct 59 ms 21464 KB Output is correct
31 Correct 70 ms 21680 KB Output is correct
32 Correct 63 ms 21660 KB Output is correct
33 Correct 66 ms 21756 KB Output is correct
34 Correct 61 ms 21656 KB Output is correct
35 Correct 65 ms 21660 KB Output is correct
36 Correct 65 ms 21664 KB Output is correct
37 Correct 75 ms 21836 KB Output is correct
38 Correct 66 ms 21740 KB Output is correct
39 Correct 64 ms 21780 KB Output is correct
40 Correct 65 ms 21876 KB Output is correct
41 Correct 63 ms 21792 KB Output is correct
42 Correct 66 ms 21656 KB Output is correct
43 Correct 63 ms 21660 KB Output is correct
44 Correct 71 ms 21780 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21656 KB Output is correct
2 Correct 71 ms 21784 KB Output is correct
3 Correct 69 ms 21676 KB Output is correct
4 Correct 62 ms 21760 KB Output is correct
5 Correct 62 ms 21732 KB Output is correct
6 Correct 63 ms 21660 KB Output is correct
7 Correct 65 ms 21676 KB Output is correct
8 Correct 65 ms 21792 KB Output is correct
9 Correct 65 ms 21780 KB Output is correct
10 Correct 79 ms 21776 KB Output is correct
11 Correct 67 ms 21820 KB Output is correct
12 Correct 69 ms 21832 KB Output is correct
13 Correct 65 ms 21664 KB Output is correct
14 Correct 82 ms 21816 KB Output is correct
15 Correct 66 ms 21816 KB Output is correct
16 Correct 71 ms 21644 KB Output is correct
17 Correct 68 ms 21872 KB Output is correct
18 Correct 67 ms 21664 KB Output is correct
19 Correct 183 ms 33400 KB Output is correct
20 Correct 185 ms 33088 KB Output is correct
21 Correct 129 ms 33056 KB Output is correct
22 Correct 122 ms 32848 KB Output is correct
23 Correct 96 ms 26796 KB Output is correct
24 Correct 95 ms 26772 KB Output is correct
25 Correct 131 ms 33388 KB Output is correct
26 Correct 137 ms 33372 KB Output is correct
27 Correct 149 ms 33232 KB Output is correct
28 Correct 168 ms 33372 KB Output is correct
29 Correct 144 ms 33224 KB Output is correct
30 Correct 101 ms 26888 KB Output is correct
31 Correct 146 ms 33348 KB Output is correct
32 Correct 166 ms 33036 KB Output is correct
33 Correct 102 ms 26972 KB Output is correct
34 Correct 143 ms 33176 KB Output is correct
35 Correct 113 ms 32628 KB Output is correct
36 Correct 98 ms 26892 KB Output is correct
37 Correct 94 ms 26900 KB Output is correct
38 Correct 165 ms 33096 KB Output is correct
39 Correct 108 ms 33348 KB Output is correct
40 Correct 131 ms 28516 KB Output is correct
41 Correct 262 ms 33376 KB Output is correct
42 Correct 59 ms 32848 KB Output is correct
43 Correct 81 ms 21940 KB Output is correct
44 Correct 75 ms 21752 KB Output is correct
45 Correct 64 ms 21676 KB Output is correct
46 Correct 59 ms 21484 KB Output is correct
47 Correct 70 ms 21660 KB Output is correct
48 Correct 64 ms 21660 KB Output is correct
49 Correct 65 ms 21664 KB Output is correct
50 Correct 62 ms 21692 KB Output is correct
51 Correct 64 ms 21780 KB Output is correct
52 Correct 58 ms 21464 KB Output is correct
53 Correct 66 ms 21740 KB Output is correct
54 Correct 59 ms 21464 KB Output is correct
55 Correct 70 ms 21680 KB Output is correct
56 Correct 63 ms 21660 KB Output is correct
57 Correct 66 ms 21756 KB Output is correct
58 Correct 61 ms 21656 KB Output is correct
59 Correct 65 ms 21660 KB Output is correct
60 Correct 65 ms 21664 KB Output is correct
61 Correct 75 ms 21836 KB Output is correct
62 Correct 66 ms 21740 KB Output is correct
63 Correct 64 ms 21780 KB Output is correct
64 Correct 65 ms 21876 KB Output is correct
65 Correct 63 ms 21792 KB Output is correct
66 Correct 66 ms 21656 KB Output is correct
67 Correct 63 ms 21660 KB Output is correct
68 Correct 71 ms 21780 KB Output is correct
69 Correct 158 ms 32596 KB Output is correct
70 Correct 180 ms 33276 KB Output is correct
71 Correct 102 ms 26928 KB Output is correct
72 Correct 94 ms 26872 KB Output is correct
73 Correct 97 ms 26892 KB Output is correct
74 Correct 118 ms 32836 KB Output is correct
75 Correct 93 ms 27000 KB Output is correct
76 Correct 149 ms 33384 KB Output is correct
77 Correct 158 ms 32796 KB Output is correct
78 Correct 102 ms 26780 KB Output is correct
79 Correct 95 ms 26808 KB Output is correct
80 Correct 119 ms 32500 KB Output is correct
81 Correct 95 ms 26784 KB Output is correct
82 Correct 150 ms 33336 KB Output is correct
83 Correct 159 ms 33048 KB Output is correct
84 Correct 94 ms 26780 KB Output is correct
85 Correct 97 ms 27008 KB Output is correct
86 Correct 142 ms 32692 KB Output is correct
87 Correct 149 ms 33288 KB Output is correct
88 Correct 102 ms 27036 KB Output is correct
89 Correct 136 ms 32888 KB Output is correct
90 Correct 143 ms 33348 KB Output is correct
91 Correct 99 ms 26784 KB Output is correct
92 Correct 131 ms 32864 KB Output is correct
93 Correct 94 ms 26784 KB Output is correct
94 Correct 95 ms 26776 KB Output is correct
95 Correct 93 ms 26776 KB Output is correct
96 Correct 192 ms 33084 KB Output is correct
97 Correct 115 ms 33348 KB Output is correct
98 Correct 122 ms 28480 KB Output is correct
99 Correct 240 ms 33516 KB Output is correct
100 Correct 64 ms 32836 KB Output is correct