/**
____ ____ ____ ____ ____ ____
||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 = 1e6 + 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 + min(tree[left_child].rb - tree[left_child].sub,
tree[right_child].rb - tree[right_child].sub);
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;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
201 ms |
67748 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
