Submission #734524

#	Time	Username	Problem	Language	Result	Execution time	Memory
734524		danikoynov	Homework (CEOI22_homework)	C++14	100 / 100	290 ms	112044 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct node
{
    int left, right;
    int type; /// 0 - ?; 1 - min; 2 - max;

    int lb, rb, sub;
    node()
    {
        left = -1;
        right = -1;
        type = -1;
        sub = 0;
        lb = 1e9;
        rb = -1e9;
        sub = 0;
    }
};

const int maxn = 2e6 + 10;

node tree[maxn];
string s;
int last_node;
void create_tree()
{
    int len = s.size();

    stack < int > st;
    int i = 0;
    while(i < len)
    {
        ///cout << i << endl;
        if (s[i] == 'm')
        {
            ++ last_node;
            if (!st.empty())
            {   ///cout << "here " << i << endl;
                int ver = st.top();///cout << ver << " : " << tree[ver].left << endl;
                if (tree[ver].left == -1)
                    tree[ver].left = last_node;
                else
                if (tree[ver].right == -1)
                {
                    ///cout << "yep" << endl;
                    tree[ver].right = last_node;
                }
            }
            if (s[i + 1] == 'i')
                tree[last_node].type = 1;
            else
                tree[last_node].type = 2;
            st.push(last_node);
            i += 4;
        }
        else
        if (s[i] == '?')
        {

            ++ last_node;
            tree[last_node].sub = 1;
            if (!st.empty())
            {
                int ver = st.top();

                if (tree[ver].left == -1)
                    tree[ver].left = last_node;
                else
                if (tree[ver].right == -1)
                {
                    ///cout << "wow " << ver << endl;
                    tree[ver].right = last_node;
                }
            }
            tree[last_node].type = 0;
            i ++;
        }
        else
        {
            i ++;
        }
        while(!st.empty() && tree[st.top()].right != -1 &&
              tree[st.top()].left != -1)
                st.pop();
    }
}

void dfs(int v)
{
    ///cout << v << " : " << tree[v].type <<  " " << tree[v].left << " " << tree[v].right <<endl;
    if (tree[v].left == -1)
    {
        tree[v].lb = tree[v].rb = 1;
        return;
    }

    int left_child = tree[v].left;
    int right_child = tree[v].right;
        dfs(left_child);
        dfs(right_child);

    tree[v].sub = tree[left_child].sub + tree[right_child].sub;
    if (tree[v].type == 1)
    {
        tree[v].lb = min(tree[left_child].lb, tree[right_child].lb);
        tree[v].rb = tree[left_child].rb + tree[right_child].rb - 1;

        /**for (int x = 1; x <= tree[v].sub; x ++)
        {
            bool found = false;
            ///cout << v << " : " << x << " " << tree[left_child].lb << " " << tree[right_child].rb << endl;
            if ((x >= tree[left_child].lb || x >= tree[right_child].lb) &&
                x < tree[left_child].rb + tree[right_child].rb)
                    found = true;
            //if (x >= tree[right_child].lb &&
              //  (tree[v].sub - x) > (tree[left_child].sub - tree[left_child].rb))
                //    found = true;
            if (found)
            {
                //cout << "found" << endl;
                tree[v].rb = x;
                tree[v].lb = min(tree[v].lb, x);
            }
        }*/

        ///cout << v << " " << tree[v].lb << " " << tree[v].rb << endl;
    }
    else
    {
        tree[v].rb = tree[v].sub + max(tree[left_child].rb - tree[left_child].sub,
                                            tree[right_child].rb - tree[right_child].sub);
                                            ///cout << tree[v].rb << endl;
        tree[v].lb = tree[left_child].lb - tree[left_child].sub + tree[right_child].lb - tree[right_child].sub  + tree[v].sub;
        ///cout << tree[v].lb << endl;
        /**for (int x = 1; x <= tree[v].sub; x ++)
        {
            bool found = false;
            if ((tree[v].sub - x >= tree[left_child].sub - tree[left_child].rb ||
                 tree[v].sub - x >= tree[right_child].sub - tree[right_child].rb) &&
                tree[v].sub - x < tree[left_child].sub - tree[left_child].lb +
                                tree[right_child].sub - tree[right_child].lb + 1)
                                    found = true;
            if (found)
            {
                //tree[v].rb = x;
                //cout << "pos " << x << endl;
                ///tree[v].lb = min(tree[v].lb, x);
            }
        }*/
    }

}
void solve()
{
    cin >> s;
    create_tree();
    dfs(1);
    cout << tree[1].rb - tree[1].lb + 1 << endl;

}

int main()
{
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34