oj.uz

Submission #936763

# Submission time Handle Problem Language Result Execution time Memory
936763 2024-03-02T16:58:58 Z ace5 Crossing (JOI21_crossing) C++17
100 / 100
 2174 ms 48072 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int mod = int(1e9)+7,pp = 101;

int toint(char c)
{
    return (c == 'J' ? 0 : (c == 'O' ? 1 : 2));
}

vector<int> segTree;
vector<int> p;
vector<int> st;

int binpow(int a,int b)
{
    return (b == 0 ? 1 : (b%2 == 0 ? binpow((a*a)%mod,b/2) : (a*binpow(a,b-1))%mod));
}
int del(int a,int b)
{
    return (a*binpow(b,mod-2))%mod;
}

int mrg(int a,int b,int lb,int rb)
{
    return (a*st[rb-lb+1]+ b)%mod;
}

void push(int l,int r,int indV)
{
    if(p[indV] == -1)
        return ;
    if(l == r)
    {
        segTree[indV] = p[indV];
        p[indV] = -1;
        return ;
    }
    segTree[indV] = (p[indV]*del((st[r-l+1]+mod-1)%mod,pp-1))%mod;
    p[indV*2+1] = p[indV];
    p[indV*2+2] = p[indV];
    p[indV] = -1;
    return ;
}

void modify(int lx,int rx,int x,int l,int r,int indV)
{
    push(l,r,indV);
    if(l > rx || r < lx)
        return ;
    else if(l >= lx && r <= rx)
    {
        p[indV] = x;
        push(l,r,indV);
        return ;
    }
    int m=(l+r)/2;
    modify(lx,rx,x,l,m,indV*2+1);
    modify(lx,rx,x,m+1,r,indV*2+2);
    segTree[indV] = mrg(segTree[indV*2+1],segTree[indV*2+2],m+1,r);
}
void print_ans(set<int> & hh)
{
    cout << (hh.find(segTree[0]) != hh.end() ? "Yes\n" : "No\n");
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;

    vector<vector<int>> s = {{},{},{}};
    string a,b,c;
    cin >> a >> b >> c;
    for(int i = 0;i < a.size();++i)
    {
        s[0].push_back(toint(a[i]));
    }
    for(int i = 0;i < b.size();++i)
    {
        s[1].push_back(toint(b[i]));
    }
    for(int i = 0;i < c.size();++i)
    {
        s[2].push_back(toint(c[i]));
    }
    set<vector<int>> ck;
    ck.insert(s[0]);
    ck.insert(s[1]);
    ck.insert(s[2]);
    while(true)
    {
        int u = s.size();
        for(int j =0;j < u;++j)
        {
            for(int i = j+1;i < u;++i)
            {
                vector<int> ne(n);
                for(int u = 0;u < n;++u)
                {
                    ne[u] = (s[i][u] == s[j][u] ? s[i][u] : 3-s[i][u]-s[j][u]);
                }
                if(ck.find(ne) == ck.end())
                {
                    ck.insert(ne);
                    s.push_back(ne);
                }
            }
        }
        if(s.size() == u)
            break;
    }
    set<int> hh;
    st.resize(n+1);
    st[0] = 1;
    for(int i =1;i <= n;++i)
    {
        st[i] = (st[i-1]*pp)%mod;
    }
    for(int j = 0;j < s.size();++j)
    {
        int th = 0;
        for(int k = 0;k < s[j].size();++k)
        {
            th *= pp;
            th += s[j][k];
            th = th%mod;
        }
        hh.insert(th);
    }
    segTree.resize(4*n);
    p.resize(4*n);
    for(int j = 0;j < 4*n;++j)
        p[j] = -1;
    int q;
    cin >> q;
    string t0;
    cin >> t0;
    for(int j = 0;j < t0.size();++j)
    {
        modify(j,j,toint(t0[j]),0,n-1,0);
    }
    print_ans(hh);
    while(q--)
    {
        int l,r;
        char c;
        cin >> l >> r >> c;
        int f = toint(c);
        modify(l-1,r-1,f,0,n-1,0);
        print_ans(hh);
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0;i < a.size();++i)
      |                   ~~^~~~~~~~~~
Main.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0;i < b.size();++i)
      |                   ~~^~~~~~~~~~
Main.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0;i < c.size();++i)
      |                   ~~^~~~~~~~~~
Main.cpp:116:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
  116 |         if(s.size() == u)
      |            ~~~~~~~~~^~~~
Main.cpp:126:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int j = 0;j < s.size();++j)
      |                   ~~^~~~~~~~~~
Main.cpp:129:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for(int k = 0;k < s[j].size();++k)
      |                       ~~^~~~~~~~~~~~~
Main.cpp:145:21: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int j = 0;j < t0.size();++j)
      |                   ~~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1868 KB Output is correct
2 Correct 267 ms 1872 KB Output is correct
3 Correct 373 ms 1876 KB Output is correct
4 Correct 157 ms 1872 KB Output is correct
5 Correct 139 ms 1864 KB Output is correct
6 Correct 152 ms 2036 KB Output is correct
7 Correct 147 ms 1952 KB Output is correct
8 Correct 161 ms 2060 KB Output is correct
9 Correct 158 ms 1876 KB Output is correct
10 Correct 151 ms 1872 KB Output is correct
11 Correct 157 ms 2120 KB Output is correct
12 Correct 157 ms 1876 KB Output is correct
13 Correct 155 ms 1972 KB Output is correct
14 Correct 146 ms 1872 KB Output is correct
15 Correct 166 ms 1836 KB Output is correct
16 Correct 150 ms 1960 KB Output is correct
17 Correct 156 ms 2164 KB Output is correct
18 Correct 386 ms 2072 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1868 KB Output is correct
2 Correct 267 ms 1872 KB Output is correct
3 Correct 373 ms 1876 KB Output is correct
4 Correct 157 ms 1872 KB Output is correct
5 Correct 139 ms 1864 KB Output is correct
6 Correct 152 ms 2036 KB Output is correct
7 Correct 147 ms 1952 KB Output is correct
8 Correct 161 ms 2060 KB Output is correct
9 Correct 158 ms 1876 KB Output is correct
10 Correct 151 ms 1872 KB Output is correct
11 Correct 157 ms 2120 KB Output is correct
12 Correct 157 ms 1876 KB Output is correct
13 Correct 155 ms 1972 KB Output is correct
14 Correct 146 ms 1872 KB Output is correct
15 Correct 166 ms 1836 KB Output is correct
16 Correct 150 ms 1960 KB Output is correct
17 Correct 156 ms 2164 KB Output is correct
18 Correct 386 ms 2072 KB Output is correct
19 Correct 1803 ms 24536 KB Output is correct
20 Correct 2039 ms 24512 KB Output is correct
21 Correct 402 ms 23208 KB Output is correct
22 Correct 509 ms 20964 KB Output is correct
23 Correct 242 ms 3600 KB Output is correct
24 Correct 288 ms 3664 KB Output is correct
25 Correct 391 ms 24348 KB Output is correct
26 Correct 574 ms 24520 KB Output is correct
27 Correct 802 ms 24276 KB Output is correct
28 Correct 835 ms 24704 KB Output is correct
29 Correct 697 ms 23844 KB Output is correct
30 Correct 384 ms 3668 KB Output is correct
31 Correct 732 ms 24388 KB Output is correct
32 Correct 686 ms 22536 KB Output is correct
33 Correct 316 ms 3632 KB Output is correct
34 Correct 733 ms 24420 KB Output is correct
35 Correct 357 ms 18624 KB Output is correct
36 Correct 263 ms 3696 KB Output is correct
37 Correct 264 ms 3664 KB Output is correct
38 Correct 1774 ms 24376 KB Output is correct
39 Correct 210 ms 24308 KB Output is correct
40 Correct 403 ms 17076 KB Output is correct
41 Correct 2127 ms 24652 KB Output is correct
42 Correct 129 ms 24320 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1868 KB Output is correct
2 Correct 267 ms 1872 KB Output is correct
3 Correct 373 ms 1876 KB Output is correct
4 Correct 157 ms 1872 KB Output is correct
5 Correct 139 ms 1864 KB Output is correct
6 Correct 152 ms 2036 KB Output is correct
7 Correct 147 ms 1952 KB Output is correct
8 Correct 161 ms 2060 KB Output is correct
9 Correct 158 ms 1876 KB Output is correct
10 Correct 151 ms 1872 KB Output is correct
11 Correct 157 ms 2120 KB Output is correct
12 Correct 157 ms 1876 KB Output is correct
13 Correct 155 ms 1972 KB Output is correct
14 Correct 146 ms 1872 KB Output is correct
15 Correct 166 ms 1836 KB Output is correct
16 Correct 150 ms 1960 KB Output is correct
17 Correct 156 ms 2164 KB Output is correct
18 Correct 386 ms 2072 KB Output is correct
19 Correct 253 ms 2056 KB Output is correct
20 Correct 372 ms 1988 KB Output is correct
21 Correct 149 ms 2132 KB Output is correct
22 Correct 139 ms 2008 KB Output is correct
23 Correct 147 ms 1876 KB Output is correct
24 Correct 154 ms 1876 KB Output is correct
25 Correct 159 ms 2132 KB Output is correct
26 Correct 144 ms 2004 KB Output is correct
27 Correct 155 ms 1912 KB Output is correct
28 Correct 142 ms 2128 KB Output is correct
29 Correct 158 ms 1892 KB Output is correct
30 Correct 135 ms 1872 KB Output is correct
31 Correct 153 ms 1876 KB Output is correct
32 Correct 148 ms 1920 KB Output is correct
33 Correct 163 ms 1956 KB Output is correct
34 Correct 140 ms 1820 KB Output is correct
35 Correct 155 ms 1912 KB Output is correct
36 Correct 164 ms 1876 KB Output is correct
37 Correct 155 ms 2028 KB Output is correct
38 Correct 165 ms 2132 KB Output is correct
39 Correct 154 ms 1848 KB Output is correct
40 Correct 164 ms 2068 KB Output is correct
41 Correct 154 ms 2112 KB Output is correct
42 Correct 162 ms 1880 KB Output is correct
43 Correct 154 ms 2020 KB Output is correct
44 Correct 163 ms 2000 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 1868 KB Output is correct
2 Correct 267 ms 1872 KB Output is correct
3 Correct 373 ms 1876 KB Output is correct
4 Correct 157 ms 1872 KB Output is correct
5 Correct 139 ms 1864 KB Output is correct
6 Correct 152 ms 2036 KB Output is correct
7 Correct 147 ms 1952 KB Output is correct
8 Correct 161 ms 2060 KB Output is correct
9 Correct 158 ms 1876 KB Output is correct
10 Correct 151 ms 1872 KB Output is correct
11 Correct 157 ms 2120 KB Output is correct
12 Correct 157 ms 1876 KB Output is correct
13 Correct 155 ms 1972 KB Output is correct
14 Correct 146 ms 1872 KB Output is correct
15 Correct 166 ms 1836 KB Output is correct
16 Correct 150 ms 1960 KB Output is correct
17 Correct 156 ms 2164 KB Output is correct
18 Correct 386 ms 2072 KB Output is correct
19 Correct 1803 ms 24536 KB Output is correct
20 Correct 2039 ms 24512 KB Output is correct
21 Correct 402 ms 23208 KB Output is correct
22 Correct 509 ms 20964 KB Output is correct
23 Correct 242 ms 3600 KB Output is correct
24 Correct 288 ms 3664 KB Output is correct
25 Correct 391 ms 24348 KB Output is correct
26 Correct 574 ms 24520 KB Output is correct
27 Correct 802 ms 24276 KB Output is correct
28 Correct 835 ms 24704 KB Output is correct
29 Correct 697 ms 23844 KB Output is correct
30 Correct 384 ms 3668 KB Output is correct
31 Correct 732 ms 24388 KB Output is correct
32 Correct 686 ms 22536 KB Output is correct
33 Correct 316 ms 3632 KB Output is correct
34 Correct 733 ms 24420 KB Output is correct
35 Correct 357 ms 18624 KB Output is correct
36 Correct 263 ms 3696 KB Output is correct
37 Correct 264 ms 3664 KB Output is correct
38 Correct 1774 ms 24376 KB Output is correct
39 Correct 210 ms 24308 KB Output is correct
40 Correct 403 ms 17076 KB Output is correct
41 Correct 2127 ms 24652 KB Output is correct
42 Correct 129 ms 24320 KB Output is correct
43 Correct 253 ms 2056 KB Output is correct
44 Correct 372 ms 1988 KB Output is correct
45 Correct 149 ms 2132 KB Output is correct
46 Correct 139 ms 2008 KB Output is correct
47 Correct 147 ms 1876 KB Output is correct
48 Correct 154 ms 1876 KB Output is correct
49 Correct 159 ms 2132 KB Output is correct
50 Correct 144 ms 2004 KB Output is correct
51 Correct 155 ms 1912 KB Output is correct
52 Correct 142 ms 2128 KB Output is correct
53 Correct 158 ms 1892 KB Output is correct
54 Correct 135 ms 1872 KB Output is correct
55 Correct 153 ms 1876 KB Output is correct
56 Correct 148 ms 1920 KB Output is correct
57 Correct 163 ms 1956 KB Output is correct
58 Correct 140 ms 1820 KB Output is correct
59 Correct 155 ms 1912 KB Output is correct
60 Correct 164 ms 1876 KB Output is correct
61 Correct 155 ms 2028 KB Output is correct
62 Correct 165 ms 2132 KB Output is correct
63 Correct 154 ms 1848 KB Output is correct
64 Correct 164 ms 2068 KB Output is correct
65 Correct 154 ms 2112 KB Output is correct
66 Correct 162 ms 1880 KB Output is correct
67 Correct 154 ms 2020 KB Output is correct
68 Correct 163 ms 2000 KB Output is correct
69 Correct 1572 ms 39800 KB Output is correct
70 Correct 2039 ms 44796 KB Output is correct
71 Correct 267 ms 2388 KB Output is correct
72 Correct 258 ms 2280 KB Output is correct
73 Correct 267 ms 2644 KB Output is correct
74 Correct 394 ms 21468 KB Output is correct
75 Correct 261 ms 2384 KB Output is correct
76 Correct 393 ms 25424 KB Output is correct
77 Correct 587 ms 21632 KB Output is correct
78 Correct 268 ms 2260 KB Output is correct
79 Correct 262 ms 2128 KB Output is correct
80 Correct 480 ms 32404 KB Output is correct
81 Correct 245 ms 3412 KB Output is correct
82 Correct 442 ms 44344 KB Output is correct
83 Correct 600 ms 41740 KB Output is correct
84 Correct 274 ms 3244 KB Output is correct
85 Correct 264 ms 3200 KB Output is correct
86 Correct 923 ms 34948 KB Output is correct
87 Correct 857 ms 44384 KB Output is correct
88 Correct 438 ms 3456 KB Output is correct
89 Correct 679 ms 40380 KB Output is correct
90 Correct 708 ms 44320 KB Output is correct
91 Correct 391 ms 3156 KB Output is correct
92 Correct 385 ms 33384 KB Output is correct
93 Correct 272 ms 3300 KB Output is correct
94 Correct 266 ms 3208 KB Output is correct
95 Correct 281 ms 3068 KB Output is correct
96 Correct 1806 ms 22852 KB Output is correct
97 Correct 291 ms 44116 KB Output is correct
98 Correct 418 ms 32876 KB Output is correct
99 Correct 2174 ms 48072 KB Output is correct
100 Correct 169 ms 47444 KB Output is correct