oj.uz

Submission #419753

# Submission time Handle Problem Language Result Execution time Memory
419753 2021-06-07T12:16:59 Z schse Crossing (JOI21_crossing) C++17
100 / 100
 6367 ms 73364 KB 
#include <bits/stdc++.h>
using namespace std;

string combine(const string &a, const string &b)
{
    string c = a;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == b[i])
            c[i] = a[i];
        else if (a[i] == 'J')
            c[i] = (b[i] == 'I' ? 'O' : 'I');
        else if (a[i] == 'O')
            c[i] = (b[i] == 'I' ? 'J' : 'I');
        else if (a[i] == 'I')
            c[i] = (b[i] == 'J' ? 'O' : 'J');
    }
    return c;
}

struct treenode
{
    pair<bool, char> target;
    char lazzy = ' ';
    vector<pair<bool, char>> strings; //singelchar, char
    vector<bool> isidentical;
};

pair<bool, char> operator+(const pair<bool, char> &a, const pair<bool, char> &b)
{
    return {a.first && b.first && a.second == b.second, a.second};
}

vector<pair<bool, char>> operator+(const vector<pair<bool, char>> &a, const vector<pair<bool, char>> &b)
{
    vector<pair<bool, char>> c;
    for (int i = 0; i < a.size(); i++)
        c.push_back(a[i] + b[i]);
    return c;
}

vector<bool> operator&&(const vector<bool> &a, const vector<bool> &b)
{
    vector<bool> c;
    for (int i = 0; i < a.size(); i++)
        c.push_back(a[i] && b[i]);
    return c;
}

treenode operator+(treenode a, treenode b)
{
    return {
        a.target + b.target,
        ' ',
        a.strings + b.strings,
        a.isidentical && b.isidentical,
    };
}

struct setgtree
{
    vector<treenode> tree = vector<treenode>(524288 + 5);

    void pushdown(int i)
    {
        if (tree[i].lazzy == ' ')
            return;
        tree[i * 2].lazzy = tree[i * 2 + 1].lazzy = tree[i].lazzy;
        tree[i * 2].target = tree[i * 2 + 1].target = {true, tree[i].lazzy};

        for (int e = 0; e < tree[i * 2].strings.size(); e++)
            tree[i * 2].isidentical[e] = tree[i * 2].strings[e] == tree[i * 2].target;
        for (int e = 0; e < tree[i * 2 + 1].strings.size(); e++)
            tree[i * 2 + 1].isidentical[e] = tree[i * 2 + 1].strings[e] == tree[i * 2 + 1].target;

        tree[i].lazzy = ' ';
    }

    treenode init(int index, int b, int e, const string &T, const vector<string> &S)
    {
        if (e - b == 1)
        {
            tree[index].target = {true, T[b]};
            for (int i = 0; i < S.size(); i++)
            {
                tree[index].strings.push_back({true, S[i][b]});
                tree[index].isidentical.push_back(S[i][b] == T[b]);
            }
            return tree[index];
        }
        init(index * 2, b, (e + b) / 2, T, S);
        init(index * 2 + 1, (b + e) / 2, e, T, S);
        tree[index] = tree[index * 2] + tree[index * 2 + 1];
        return tree[index];
    }

    treenode upd(int index, int b, int e, int l, int r, char c)
    {
        if (l <= b && e <= r)
        {
            tree[index].target = {true, c};
            for (int i = 0; i < tree[index].strings.size(); i++)
                tree[index].isidentical[i] = tree[index].strings[i] == tree[index].target;
            tree[index].lazzy = c;
            return tree[index];
        }
        if (r <= b || e <= l)
            return tree[index];
        pushdown(index);
        upd(index * 2, b, (e + b) / 2, l, r, c);
        upd(index * 2 + 1, (b + e) / 2, e, l, r, c);
        tree[index] = tree[index * 2] + tree[index * 2 + 1];
        return tree[index];
    }
} tree;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    set<string> str;
    vector<string> vs;
    string s;
    cin >> N >> s;
    if (str.insert(s).second)
        vs.push_back(s);
    cin >> s;
    if (str.insert(s).second)
        vs.push_back(s);
    cin >> s >> Q;
    if (str.insert(s).second)
        vs.push_back(s);
    for (int i = 0; i < vs.size(); i++)
    {
        for (int e = 0; e < i; e++)
        {
            if (e != i && str.insert(combine(vs[i], vs[e])).second)
                vs.push_back(combine(vs[i], vs[e]));
        }
    }

    string T;
    cin >> T;

    tree.init(1, 0, N, T, vs);
    bool b = false;
    for (const bool &s : tree.tree[1].isidentical)
        b |= s;
    if (b)
        cout << "Yes\n";
    else
        cout << "No\n";
    for (int i = 0, b, e; i < Q; i++)
    {
        char c;
        cin >> b >> e >> c;
        tree.upd(1, 0, N, b - 1, e, c);
        bool x = false;
        for (const bool &s : tree.tree[1].isidentical)
            x |= s;
        if (x)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'std::string combine(const string&, const string&)':
Main.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'std::vector<std::pair<bool, char> > operator+(const std::vector<std::pair<bool, char> >&, const std::vector<std::pair<bool, char> >&)':
Main.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In function 'std::vector<bool> operator&&(const std::vector<bool>&, const std::vector<bool>&)':
Main.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp: In member function 'void setgtree::pushdown(int)':
Main.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int e = 0; e < tree[i * 2].strings.size(); e++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int e = 0; e < tree[i * 2 + 1].strings.size(); e++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In member function 'treenode setgtree::init(int, int, int, const string&, const std::vector<std::__cxx11::basic_string<char> >&)':
Main.cpp:84:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             for (int i = 0; i < S.size(); i++)
      |                             ~~^~~~~~~~~~
Main.cpp: In member function 'treenode setgtree::upd(int, int, int, int, int, char)':
Main.cpp:102:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<bool, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             for (int i = 0; i < tree[index].strings.size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < vs.size(); i++)
      |                     ~~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 37784 KB Output is correct
2 Correct 696 ms 37916 KB Output is correct
3 Correct 863 ms 37848 KB Output is correct
4 Correct 576 ms 37824 KB Output is correct
5 Correct 559 ms 37732 KB Output is correct
6 Correct 570 ms 37732 KB Output is correct
7 Correct 558 ms 37784 KB Output is correct
8 Correct 618 ms 37812 KB Output is correct
9 Correct 614 ms 37748 KB Output is correct
10 Correct 594 ms 37800 KB Output is correct
11 Correct 623 ms 37832 KB Output is correct
12 Correct 610 ms 37788 KB Output is correct
13 Correct 640 ms 37976 KB Output is correct
14 Correct 589 ms 37884 KB Output is correct
15 Correct 607 ms 37876 KB Output is correct
16 Correct 648 ms 37844 KB Output is correct
17 Correct 624 ms 37848 KB Output is correct
18 Correct 637 ms 37884 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 37784 KB Output is correct
2 Correct 696 ms 37916 KB Output is correct
3 Correct 863 ms 37848 KB Output is correct
4 Correct 576 ms 37824 KB Output is correct
5 Correct 559 ms 37732 KB Output is correct
6 Correct 570 ms 37732 KB Output is correct
7 Correct 558 ms 37784 KB Output is correct
8 Correct 618 ms 37812 KB Output is correct
9 Correct 614 ms 37748 KB Output is correct
10 Correct 594 ms 37800 KB Output is correct
11 Correct 623 ms 37832 KB Output is correct
12 Correct 610 ms 37788 KB Output is correct
13 Correct 640 ms 37976 KB Output is correct
14 Correct 589 ms 37884 KB Output is correct
15 Correct 607 ms 37876 KB Output is correct
16 Correct 648 ms 37844 KB Output is correct
17 Correct 624 ms 37848 KB Output is correct
18 Correct 637 ms 37884 KB Output is correct
19 Correct 3029 ms 63692 KB Output is correct
20 Correct 3098 ms 63676 KB Output is correct
21 Correct 2109 ms 62316 KB Output is correct
22 Correct 1990 ms 59620 KB Output is correct
23 Correct 1244 ms 39488 KB Output is correct
24 Correct 1302 ms 39216 KB Output is correct
25 Correct 2261 ms 63704 KB Output is correct
26 Correct 2142 ms 63756 KB Output is correct
27 Correct 2683 ms 63612 KB Output is correct
28 Correct 2890 ms 63680 KB Output is correct
29 Correct 2528 ms 62884 KB Output is correct
30 Correct 1381 ms 39132 KB Output is correct
31 Correct 2699 ms 63624 KB Output is correct
32 Correct 2620 ms 61368 KB Output is correct
33 Correct 1387 ms 39152 KB Output is correct
34 Correct 2770 ms 63688 KB Output is correct
35 Correct 1949 ms 57020 KB Output is correct
36 Correct 1302 ms 39132 KB Output is correct
37 Correct 1314 ms 39144 KB Output is correct
38 Correct 2407 ms 63684 KB Output is correct
39 Correct 1742 ms 63784 KB Output is correct
40 Correct 2110 ms 54784 KB Output is correct
41 Correct 3417 ms 63864 KB Output is correct
42 Correct 216 ms 63804 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 37784 KB Output is correct
2 Correct 696 ms 37916 KB Output is correct
3 Correct 863 ms 37848 KB Output is correct
4 Correct 576 ms 37824 KB Output is correct
5 Correct 559 ms 37732 KB Output is correct
6 Correct 570 ms 37732 KB Output is correct
7 Correct 558 ms 37784 KB Output is correct
8 Correct 618 ms 37812 KB Output is correct
9 Correct 614 ms 37748 KB Output is correct
10 Correct 594 ms 37800 KB Output is correct
11 Correct 623 ms 37832 KB Output is correct
12 Correct 610 ms 37788 KB Output is correct
13 Correct 640 ms 37976 KB Output is correct
14 Correct 589 ms 37884 KB Output is correct
15 Correct 607 ms 37876 KB Output is correct
16 Correct 648 ms 37844 KB Output is correct
17 Correct 624 ms 37848 KB Output is correct
18 Correct 637 ms 37884 KB Output is correct
19 Correct 1335 ms 37792 KB Output is correct
20 Correct 1579 ms 37876 KB Output is correct
21 Correct 774 ms 37748 KB Output is correct
22 Correct 648 ms 37716 KB Output is correct
23 Correct 750 ms 37756 KB Output is correct
24 Correct 736 ms 37928 KB Output is correct
25 Correct 774 ms 37848 KB Output is correct
26 Correct 722 ms 37724 KB Output is correct
27 Correct 814 ms 37848 KB Output is correct
28 Correct 740 ms 37872 KB Output is correct
29 Correct 801 ms 37892 KB Output is correct
30 Correct 643 ms 37704 KB Output is correct
31 Correct 1207 ms 37804 KB Output is correct
32 Correct 1148 ms 37828 KB Output is correct
33 Correct 1216 ms 37856 KB Output is correct
34 Correct 1008 ms 37856 KB Output is correct
35 Correct 1214 ms 37840 KB Output is correct
36 Correct 1178 ms 37868 KB Output is correct
37 Correct 1172 ms 37852 KB Output is correct
38 Correct 1188 ms 37868 KB Output is correct
39 Correct 1139 ms 38040 KB Output is correct
40 Correct 1201 ms 37896 KB Output is correct
41 Correct 1184 ms 37872 KB Output is correct
42 Correct 1186 ms 37832 KB Output is correct
43 Correct 1106 ms 38040 KB Output is correct
44 Correct 1216 ms 37992 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 37784 KB Output is correct
2 Correct 696 ms 37916 KB Output is correct
3 Correct 863 ms 37848 KB Output is correct
4 Correct 576 ms 37824 KB Output is correct
5 Correct 559 ms 37732 KB Output is correct
6 Correct 570 ms 37732 KB Output is correct
7 Correct 558 ms 37784 KB Output is correct
8 Correct 618 ms 37812 KB Output is correct
9 Correct 614 ms 37748 KB Output is correct
10 Correct 594 ms 37800 KB Output is correct
11 Correct 623 ms 37832 KB Output is correct
12 Correct 610 ms 37788 KB Output is correct
13 Correct 640 ms 37976 KB Output is correct
14 Correct 589 ms 37884 KB Output is correct
15 Correct 607 ms 37876 KB Output is correct
16 Correct 648 ms 37844 KB Output is correct
17 Correct 624 ms 37848 KB Output is correct
18 Correct 637 ms 37884 KB Output is correct
19 Correct 3029 ms 63692 KB Output is correct
20 Correct 3098 ms 63676 KB Output is correct
21 Correct 2109 ms 62316 KB Output is correct
22 Correct 1990 ms 59620 KB Output is correct
23 Correct 1244 ms 39488 KB Output is correct
24 Correct 1302 ms 39216 KB Output is correct
25 Correct 2261 ms 63704 KB Output is correct
26 Correct 2142 ms 63756 KB Output is correct
27 Correct 2683 ms 63612 KB Output is correct
28 Correct 2890 ms 63680 KB Output is correct
29 Correct 2528 ms 62884 KB Output is correct
30 Correct 1381 ms 39132 KB Output is correct
31 Correct 2699 ms 63624 KB Output is correct
32 Correct 2620 ms 61368 KB Output is correct
33 Correct 1387 ms 39152 KB Output is correct
34 Correct 2770 ms 63688 KB Output is correct
35 Correct 1949 ms 57020 KB Output is correct
36 Correct 1302 ms 39132 KB Output is correct
37 Correct 1314 ms 39144 KB Output is correct
38 Correct 2407 ms 63684 KB Output is correct
39 Correct 1742 ms 63784 KB Output is correct
40 Correct 2110 ms 54784 KB Output is correct
41 Correct 3417 ms 63864 KB Output is correct
42 Correct 216 ms 63804 KB Output is correct
43 Correct 1335 ms 37792 KB Output is correct
44 Correct 1579 ms 37876 KB Output is correct
45 Correct 774 ms 37748 KB Output is correct
46 Correct 648 ms 37716 KB Output is correct
47 Correct 750 ms 37756 KB Output is correct
48 Correct 736 ms 37928 KB Output is correct
49 Correct 774 ms 37848 KB Output is correct
50 Correct 722 ms 37724 KB Output is correct
51 Correct 814 ms 37848 KB Output is correct
52 Correct 740 ms 37872 KB Output is correct
53 Correct 801 ms 37892 KB Output is correct
54 Correct 643 ms 37704 KB Output is correct
55 Correct 1207 ms 37804 KB Output is correct
56 Correct 1148 ms 37828 KB Output is correct
57 Correct 1216 ms 37856 KB Output is correct
58 Correct 1008 ms 37856 KB Output is correct
59 Correct 1214 ms 37840 KB Output is correct
60 Correct 1178 ms 37868 KB Output is correct
61 Correct 1172 ms 37852 KB Output is correct
62 Correct 1188 ms 37868 KB Output is correct
63 Correct 1139 ms 38040 KB Output is correct
64 Correct 1201 ms 37896 KB Output is correct
65 Correct 1184 ms 37872 KB Output is correct
66 Correct 1186 ms 37832 KB Output is correct
67 Correct 1106 ms 38040 KB Output is correct
68 Correct 1216 ms 37992 KB Output is correct
69 Correct 5097 ms 67380 KB Output is correct
70 Correct 6086 ms 72996 KB Output is correct
71 Correct 1609 ms 39124 KB Output is correct
72 Correct 1673 ms 39216 KB Output is correct
73 Correct 1641 ms 39260 KB Output is correct
74 Correct 2408 ms 60004 KB Output is correct
75 Correct 1663 ms 39300 KB Output is correct
76 Correct 2744 ms 64472 KB Output is correct
77 Correct 2510 ms 60036 KB Output is correct
78 Correct 1656 ms 39480 KB Output is correct
79 Correct 1634 ms 39240 KB Output is correct
80 Correct 3865 ms 63076 KB Output is correct
81 Correct 2650 ms 39688 KB Output is correct
82 Correct 4540 ms 73304 KB Output is correct
83 Correct 4313 ms 70924 KB Output is correct
84 Correct 2488 ms 39628 KB Output is correct
85 Correct 2523 ms 39620 KB Output is correct
86 Correct 4591 ms 64524 KB Output is correct
87 Correct 4877 ms 73364 KB Output is correct
88 Correct 2690 ms 39632 KB Output is correct
89 Correct 4351 ms 68912 KB Output is correct
90 Correct 4864 ms 73220 KB Output is correct
91 Correct 2634 ms 39664 KB Output is correct
92 Correct 3764 ms 64388 KB Output is correct
93 Correct 2455 ms 39692 KB Output is correct
94 Correct 2431 ms 39820 KB Output is correct
95 Correct 2528 ms 39616 KB Output is correct
96 Correct 2336 ms 63852 KB Output is correct
97 Correct 3221 ms 73116 KB Output is correct
98 Correct 3963 ms 61036 KB Output is correct
99 Correct 6367 ms 73360 KB Output is correct
100 Correct 431 ms 73168 KB Output is correct