Submission #959738

#TimeUsernameProblemLanguageResultExecution timeMemory
959738LCJLYHomework (CEOI22_homework)C++14
100 / 100
177 ms195232 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ld long double #define show(x,y) cout << y << " " << #x << endl; #define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl; #define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl; #define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl; typedef pair<long long,int>pii; //typedef pair<pii,pii>pi2; typedef array<int,3>pi2; mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); string s; int n; vector<int>v[1000005]; int cnt=0; pi2 dnc(int l, int r, int d){ if(l==r){ return {1,1,1}; } else if(s[l+1]=='i'){ int index=lower_bound(v[d].begin(),v[d].end(),l)-v[d].begin(); index=v[d][index]; pi2 a=dnc(l+4,index-1,d+1); pi2 b=dnc(index+1,r-1,d+1); return {min(a[0],b[0]),a[1]+b[1]-1,a[2]+b[2]}; } else{ int index=lower_bound(v[d].begin(),v[d].end(),l)-v[d].begin(); index=v[d][index]; pi2 a=dnc(l+4,index-1,d+1); pi2 b=dnc(index+1,r-1,d+1); return {a[0]+b[0],max(a[1]+b[2],b[1]+a[2]),a[2]+b[2]}; } } void solve(){ cin >> s; n=s.length(); int lvl=0; for(int x=0;x<n;x++){ if(s[x]=='('){ lvl++; } else if(s[x]==')'){ lvl--; } else if(s[x]==','){ v[lvl].push_back(x); } //else if(s[x]=='?') cnt++; } pi2 hold=dnc(0,n-1,1); cout << hold[1]-hold[0]+1; } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--){ solve(); } }
#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...