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;
#define Nahida ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
//#define int long long
const int N = 1e7 + 5 ;
const int mod = 1e9 + 7 ;
//const int inf = 1e17 ;
int n ;
int mid[N] ;
string s ;
int mx( int l , int r ){
if ( l == r ) return 1 ;
int ll = mid[l] ;
int cl = mx ( l+4 , ll-1 ) ;
int cr = mx ( ll+1 , r-1 ) ;
if ( s[l+1] == 'i' ) return cl + cr ;
else return min( cl , cr ) ;
}
int mn( int l , int r ){
if ( l == r ) return 1 ;
int ll = l+3 , cnt = 0 ;
while ( ll ++ ){
if ( s[ll] == '(' ) cnt ++ ;
if ( s[ll] == ')' ) cnt -- ;
if ( s[ll] == ',' && cnt == 0 ) break ;
}
int cl = mn ( l+4 , ll-1 ) ;
int cr = mn ( ll+1 , r-1 ) ;
if ( s[l+1] == 'a' ) return cl + cr ;
else return min( cl , cr ) ;
}
signed main(){
Nahida ;
cin >> s ;
for ( int i = 0 ; i < s.size() ; i ++ ) if ( s[i] == '?' ) n ++ ;
int cnt = 0 ;
stack <int> st ;
for ( int i = 0 ; i < s.size() ; i ++ ){
if ( s[i] == 'm' ) st.push(i) ;
if ( s[i] == ',' ){
mid[st.top()] = i ;
st.pop() ;
}
}
int l = mn( 0 , s.size() - 1 ) ;
int r = n-mx( 0 , s.size() - 1 )+1 ;
// cout << l << ' ' << r << endl ;
cout << r - l + 1 ;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for ( int i = 0 ; i < s.size() ; i ++ ) if ( s[i] == '?' ) n ++ ;
| ~~^~~~~~~~~~
Main.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for ( int i = 0 ; i < s.size() ; i ++ ){
| ~~^~~~~~~~~~
Main.cpp:47:6: warning: unused variable 'cnt' [-Wunused-variable]
47 | int cnt = 0 ;
| ^~~
# | 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... |