Submission #851782

#TimeUsernameProblemLanguageResultExecution timeMemory
851782AndreiHomework (CEOI22_homework)C++17
53 / 100
151 ms45852 KiB
#include <bits/stdc++.h> using namespace std; int n; string s; vector <int> posbrackets; stack <int> stk; int partner[1000005]; struct S { int sz; int l,r; S(int _sz,int _l,int _r) { sz=_sz; l=_l; r=_r; } }; S Merge(S A,S B,int type) { S ans(0,0,0); ans.sz=A.sz+B.sz; if(type==0) { ans.l=min(A.l,B.l); ans.r=(A.sz+B.sz)-(A.sz-A.r)+1-(B.sz-B.r+1)-1; } else { ans.l=(A.l-1)+B.l+1; ans.r=(A.sz+B.sz)-min(A.sz-A.r,B.sz-B.r); } return ans; } S solve(int l,int r) { S A(1,1,1),B(1,1,1); if(s[posbrackets[l]+1]=='m') A=solve(l+1,partner[l+1]); if(s[posbrackets[r]-1]==')') B=solve(partner[r-1],r-1); if(s[posbrackets[l]-1]=='x') return Merge(A,B,1); return Merge(A,B,0); } int main() { cin>>s; n=(int)s.size(); for(int i=0; i<n; i++) if(s[i]=='(' || s[i]==')') posbrackets.push_back(i); for(int i=0; i<(int)posbrackets.size(); i++) { int p=posbrackets[i]; if(s[p]=='(') stk.push(i); else { partner[stk.top()]=i; partner[i]=stk.top(); stk.pop(); } } S ans=solve(0,(int)posbrackets.size()-1); cout<<ans.r-ans.l+1<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...