제출 #1323918

#제출 시각아이디문제언어결과실행 시간메모리
1323918dzuizzHomework (CEOI22_homework)C++20
100 / 100
47 ms25760 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=1e6+5;
struct node{
  int sz,lo,hi;
};
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  string s; cin>>s;
  int n=s.size();
  vector<node> v;
  vector<bool> op; // 1-max,0-min
  for(int i=0;i<n;++i){
    char c=s[i];
    if(c=='?'){
      v.push_back({1,1,1});
    }else if(c=='m'){
      if(i+2<n && s[i+1]=='i' && s[i+2]=='n')
        op.push_back(1);
      else
        op.push_back(0);
      i+=2;
    }else if(c==')'){
      node rg=v.back(); v.pop_back();
      node lf=v.back(); v.pop_back();
      bool t=op.back(); op.pop_back();
      node cur;
      cur.sz=lf.sz+rg.sz;
      if(t){
        cur.lo=lf.lo+rg.lo;
        cur.hi=max(lf.hi+rg.sz,rg.hi+lf.sz);
      }else{
        cur.lo=min(lf.lo,rg.lo);
        cur.hi=lf.hi+rg.hi-1;
      }
      v.push_back(cur);
    }
  }
  node root=v.back();
  cout<<root.hi-root.lo+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...