Submission #1069670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069670		danikoynov	Crossing (JOI21_crossing)	C++14	100 / 100	2189 ms	225204 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

int n;
string c1, c2, c3;

unordered_set < string > st;

string action(string s1, string s2)
{
    string res;
    res.resize(n);
    for (int i = 0; i < n; i ++)
    {
        if (s1[i] == s2[i])
            res[i] = s1[i];
        else
        {
            char c = 'J';
            if (s1[i] == c || s2[i] == c)
                c = 'O';
            if (s1[i] == c || s2[i] == c)
                c = 'I';
            res[i] = c;
        }
    }
    return res;
}
void brute(string s)
{
    if (st.find(s) != st.end())
        return;

    st.insert(s);

    brute(action(s, c1));
    brute(action(s, c2));
    brute(action(s, c3));
}

/*
0 - J
1 - O
2 - I
*/

int id[256];

struct Node
{
    int cnt[3];
    int match[3];

    Node()
    {
        for (int i = 0; i < 3; i ++)
        {
            cnt[i] = match[i] = 0;
        }
    }
};

Node unite(Node lf, Node rf)
{
    Node mf;
    for (int i = 0; i < 3; i ++)
    {
        mf.cnt[i] = lf.cnt[i] + rf.cnt[i];
        mf.match[i] = lf.match[i] + rf.match[i];
    }

    return mf;
}

const int MAXN = 2e5 + 10;

struct SegmentTree
{
    Node tree[4 * MAXN];
    string pat;

    void build_tree(int root, int left, int right, string &val)
    {
        lazy[root] = 3;
        if (left == right)
        {
            tree[root] = Node();
            tree[root].cnt[id[pat[left]]] ++;
            if (val[left] == pat[left])
                tree[root].match[id[pat[left]]] ++;
            return;
        }

        int mid = (left + right) / 2;
        build_tree(root * 2, left, mid, val);
        build_tree(root * 2 + 1, mid + 1, right, val);
    
        tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);

        //cout << "here " << root << " " << left << " " << right << " " << tree[root].match[0] + tree[root].match[1] + tree[root].match[2] << endl;
    }

    int lazy[4 * MAXN];

    void push_lazy(int root, int left, int right)
    {
        if (lazy[root] == 3)
            return;
        for (int i = 0; i < 3; i ++)
        {   
            tree[root].match[i] = 0;
        }

        tree[root].match[lazy[root]] = tree[root].cnt[lazy[root]];
        
        if (left != right)
        {
            lazy[root * 2] = lazy[root];
            lazy[root * 2 + 1] = lazy[root];
        }

        lazy[root] = 3;
    }
    void update_range(int root, int left, int right, int qleft, int qright, int val)
    {
        push_lazy(root, left, right);
        if (left > qright || right < qleft)
            return;

        if (left >= qleft && right <= qright)
        {
            lazy[root] = val;
            push_lazy(root, left, right);
            return;
        }

        int mid = (left + right) / 2;
        update_range(root * 2, left, mid, qleft, qright, val);
        update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

        tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
    }
};
int q;
string t;

string val[10];
SegmentTree seg[10];

int m;

bool check_answer()
{
    for (int i = 1; i <= m; i ++)
    {
        int match = 0;
        for (int j = 0; j < 3; j ++)
            match += seg[i].tree[1].match[j];
        if (match == n)
            return true;
    }
    return false;
}

void solve()
{
    id['J'] = 0;
    id['O'] = 1;
    id['I'] = 2;
    cin >> n;
    cin >> c1 >> c2 >> c3;
    brute(c1);
    brute(c2);
    brute(c3);
    assert(st.size() < 10);

    cin >> q >> t;
    t = "#" + t;
    for (string cur : st)
    {
        m ++;
        seg[m].pat = "#" + cur;
        seg[m].build_tree(1, 1, n, t);
    }
      //  cout << cur << endl;

    //cout << "find " << t << endl;
    if (check_answer())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    for (int i = 1; i <= q; i ++)
    {
        int l, r;
        char c;
        cin >> l >> r >> c;
        for (int j = 1; j <= m; j ++)
        {
            seg[j].update_range(1, 1, n, l, r, id[c]);
        }

        if (check_answer())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

}

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
int main()
{
    speed();
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'void SegmentTree::build_tree(int, int, int, std::string&)':
Main.cpp:90:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   90 |             tree[root].cnt[id[pat[left]]] ++;
      |                                        ^
Main.cpp:92:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   92 |                 tree[root].match[id[pat[left]]] ++;
      |                                              ^
Main.cpp: In function 'void solve()':
Main.cpp:201:51: warning: array subscript has type 'char' [-Wchar-subscripts]
  201 |             seg[j].update_range(1, 1, n, l, r, id[c]);
      |                                                   ^

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