This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std ;
const int MAX = 4e6 + 10 ;
string s ;
int sz[MAX] , mark[MAX] ;
int L[MAX] , R[MAX] ;
int Lchild[MAX] , Rchild[MAX] ;
int val[MAX] ;
void dfs(int node)
{
if(mark[node])
{
sz[node] = 1 ;
L[node] = R[node] = 1 ;
return ;
}
int x = Lchild[node] , y = Rchild[node] ;
dfs(x) , dfs(y) ;
sz[node] = sz[x] + sz[y] ;
if(val[node]) //Max
L[node] = L[x] + L[y] , R[node] = max(sz[x] + R[y] , sz[y] + R[x]) ;
else
L[node] = min(L[x] , L[y]) , R[node] = R[x] + R[y] - 1 ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>s ;
stack<int>st ;
int cur = 0 ;
for(int i = 0 ; i < s.size() ; ++i)
{
if(s[i] == '(')
{
++cur ;
if(st.size())
{
if(!Lchild[st.top()])
Lchild[st.top()] = cur ;
else
Rchild[st.top()] = cur ;
}
st.push(cur) ;
val[cur] = (s[i-1] == 'x') ; //Max
}
else if(s[i] == ')')
st.pop() ;
else if(s[i] == '?')
{
++cur ;
mark[cur] = 1 ;
if(!Lchild[st.top()])
Lchild[st.top()] = cur ;
else
Rchild[st.top()] = cur ;
}
}
dfs(1) ;
return cout<<R[1] - L[1] + 1<<"\n" , 0 ;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0 ; i < s.size() ; ++i)
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |