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 rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,l,r) for(int i=l; i<r; i++)
#define all(x) x.begin(),x.end()
#define len(x) (int)x.size();
#define fi first
#define se second
#define elif else if
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
constexpr ll LINF=1001001001001001001LL;
constexpr ll MINF=1001001001001LL;
constexpr int INF=1001001001;
constexpr int MAX_N=1001001;
string S;
int sz;
vector<vector<int>> comma(MAX_N);
array<int,3> calc(int lf,int ri,int lv){
if(ri-lf==1)return {0,1,1};
int cp=*lower_bound(all(comma[lv]),lf);
array<int,3> left=calc(lf+4,cp,lv+1);
array<int,3> right=calc(cp+1,ri-1,lv+1);
array<int,3> ret={0,0,left[2]+right[2]};
if(S[lf+1]=='i'){
tie(left[0],left[1])=pii{left[2]-left[1],left[2]-left[0]};
tie(right[0],right[1])=pii{right[2]-right[1],right[2]-right[0]};
}
//TODO:make_max
ret[0]=left[0]+right[0]+1;
ret[1]=max(left[2]+right[1],right[2]+left[1]);
if(S[lf+1]=='i'){
tie(ret[0],ret[1])=pii{ret[2]-ret[1],ret[2]-ret[0]};
}
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>S;
sz=len(S);
int level=0;
rep(i,sz){
if(S[i]=='(')level++;
elif(S[i]==')')level--;
elif(S[i]==',')comma[level-1].emplace_back(i);
}
array<int,3> ans=calc(0,sz,0);
cout<<ans[1]-ans[0]<<"\n";
}
# | 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... |