結果

問題 No.2595 Parsing Challenge
ユーザー 👑 tute7627tute7627
提出日時 2024-05-04 05:21:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 659 ms / 6,000 ms
コード長 36,735 bytes
コンパイル時間 5,120 ms
コンパイル使用メモリ 263,884 KB
実行使用メモリ 191,968 KB
最終ジャッジ日時 2024-05-04 05:21:47
合計ジャッジ時間 19,506 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,944 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 6 ms
6,944 KB
testcase_21 AC 6 ms
6,940 KB
testcase_22 AC 6 ms
6,940 KB
testcase_23 AC 5 ms
6,940 KB
testcase_24 AC 6 ms
6,944 KB
testcase_25 AC 35 ms
10,848 KB
testcase_26 AC 43 ms
13,152 KB
testcase_27 AC 41 ms
12,308 KB
testcase_28 AC 40 ms
12,516 KB
testcase_29 AC 40 ms
12,644 KB
testcase_30 AC 330 ms
86,868 KB
testcase_31 AC 365 ms
91,640 KB
testcase_32 AC 350 ms
92,116 KB
testcase_33 AC 322 ms
83,300 KB
testcase_34 AC 328 ms
88,256 KB
testcase_35 AC 659 ms
92,380 KB
testcase_36 AC 628 ms
92,468 KB
testcase_37 AC 656 ms
89,580 KB
testcase_38 AC 627 ms
91,028 KB
testcase_39 AC 632 ms
88,608 KB
testcase_40 AC 19 ms
7,184 KB
testcase_41 AC 20 ms
7,184 KB
testcase_42 AC 19 ms
7,180 KB
testcase_43 AC 165 ms
191,968 KB
testcase_44 AC 202 ms
52,756 KB
testcase_45 AC 212 ms
52,568 KB
testcase_46 AC 201 ms
52,400 KB
testcase_47 AC 204 ms
52,680 KB
testcase_48 AC 217 ms
52,532 KB
testcase_49 AC 507 ms
61,160 KB
testcase_50 AC 510 ms
61,304 KB
testcase_51 AC 525 ms
62,752 KB
testcase_52 AC 334 ms
85,596 KB
testcase_53 AC 350 ms
84,520 KB
testcase_54 AC 356 ms
84,940 KB
testcase_55 AC 328 ms
84,656 KB
testcase_56 AC 332 ms
84,440 KB
testcase_57 AC 425 ms
158,492 KB
testcase_58 AC 393 ms
157,408 KB
testcase_59 AC 398 ms
157,904 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:1252:3: warning: control reaches end of non-void function [-Wreturn-type]
 1252 |   };
      |   ^

ソースコード

diff #

//#define _GLIBCXX_DEBUG

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;


#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif

#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
using ll = long long;
using ld = long double;
const ll MOD1 = 1e9+7;
const ll MOD9 = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};  
template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
  auto tmp = v;
  for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
}
template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
  rearrange(ord, head);
  rearrange(ord, tail...);
}
template<typename T> vector<int> ascend(const vector<T>&v){
  vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
  sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
  return ord;
}
template<typename T> vector<int> descend(const vector<T>&v){
  vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
  sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
  return ord;
}
template<typename T> vector<T> inv_perm(const vector<T>&ord){
  vector<T>inv(ord.size());
  for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
  return inv;
}
ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
ll modulo(ll n,ll d){return (n%d+d)%d;};
template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
int popcount(ll x){return __builtin_popcountll(x);};
int poplow(ll x){return __builtin_ctzll(x);};
int pophigh(ll x){return 63 - __builtin_clzll(x);};
template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
namespace converter{
  int dict[500];
  const string lower="abcdefghijklmnopqrstuvwxyz";
  const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  const string digit="0123456789";
  const string digit1="123456789";
  void regi_str(const string &t){
    for(int i=0;i<t.size();i++){
      dict[t[i]]=i;
    }
  }
  void regi_int(const string &t){
    for(int i=0;i<t.size();i++){
      dict[i]=t[i];
    }
  }
  vector<int>to_int(const string &s,const string &t){
    regi_str(t);
    vector<int>ret(s.size());
    for(int i=0;i<s.size();i++){
      ret[i]=dict[s[i]];
    }
    return ret;
  }
  vector<int>to_int(const string &s){
    auto t=s;
    sort(t.begin(),t.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    return to_int(s,t);
  }
  
  vector<vector<int>>to_int(const vector<string>&s,const string &t){
    regi_str(t);
    vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
    for(int i=0;i<s.size();i++){
      for(int j=0;j<s[0].size();j++){
        ret[i][j]=dict[s[i][j]];
      }
    }
    return ret;
  }
  vector<vector<int>>to_int(const vector<string>&s){
    string t;
    for(int i=0;i<s.size();i++){
      t+=s[i];
    }
    sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
    return to_int(s,t);
  }
  string to_str(const vector<int>&s,const string &t){
    regi_int(t);
    string ret;
    for(auto z:s)ret+=dict[z];
    return ret;
  }
  vector<string> to_str(const vector<vector<int>>&s,const string &t){
    regi_int(t);
    vector<string>ret(s.size());
    for(int i=0;i<s.size();i++){
      for(auto z:s[i])ret[i]+=dict[z];
    }
    return ret;
  }
}
template< typename T = int >
struct edge {
  int to;
  T cost;
  int id;
  edge():to(-1),id(-1){};
  edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
  operator int() const { return to; }
};

template<typename T>
using Graph = vector<vector<edge<T>>>;
template<typename T>
Graph<T>revgraph(const Graph<T> &g){
  Graph<T>ret(g.size());
  for(int i=0;i<g.size();i++){
    for(auto e:g[i]){
      int to = e.to;
      e.to = i;
      ret[to].push_back(e);
    }
  }
  return ret;
}
template<typename T>
Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
  Graph<T> ret(n);
  for(int es = 0; es < m; es++){
    int u,v;
    T w=1;
    cin>>u>>v;u-=indexed,v-=indexed;
    if(weighted)cin>>w;
    ret[u].emplace_back(v,w,es);
    if(!directed)ret[v].emplace_back(u,w,es);
  }
  return ret;
}
template<typename T>
Graph<T> readParent(int n,int indexed=1,bool directed=true){
  Graph<T>ret(n);
  for(int i=1;i<n;i++){
    int p;cin>>p;
    p-=indexed;
    ret[p].emplace_back(i);
    if(!directed)ret[i].emplace_back(p);
  }
  return ret;
}
template<typename T>
struct HLD{
  using D=long long;
  int n;
  vector<int>sz;//部分木サイズ
  vector<D>dep;
  vector<int>par;
  vector<int>head;
  Graph<T> &g;//隣接リスト
  vector<edge<T>>edges;//データ構造に乗せるedge列
  vector<int>in,out;//[in,out)で部分木、[ina,inb]でa~bのパス(aが上)
  vector<int>comp;//連結成分の根
  //inは頂点のindexを表す。また、edge列の下側の頂点である
  HLD(Graph<T> &g,int r=-1):g(g),n(g.size()){
    hld_build(r);
  }
  void hld_build(int root = -1){
    in.assign(n,-1);out.assign(n,-1);dep.assign(n,0);
    par.assign(n,-1);head.assign(n,-1);sz.assign(n,-1);comp.assign(n,-1);
    edges.assign(n,edge<T>());
    if(root == -1){//根がどこでも良い場合(森でも可)
      for(int i=0;i<n;i++){
        if(sz[i] == -1){
          head[i] = i;
          dfs_sz(i, 0, i);
          dfs_hld(i);
        }
      }
    }
    else{
      head[root] = root;
      dfs_sz(root, 0, root);
      dfs_hld(root);
    }
  }
  void dfs_sz(int k, D d,int r){
    sz[k] = 1;
    comp[k] = r;
	dep[k] = d;
    for(auto &e: g[k]){
      if(e.to == par[k])continue;
      par[e.to] = k;
      dfs_sz(e.to, d+e.cost, r);
      sz[k] += sz[e.to];
      if(g[k][0].to==par[k]||sz[e.to] > sz[g[k][0].to])swap(e, g[k][0]);
    }
  }
  int time = 0;
  void dfs_hld(int k){
    in[k] = time++;
    for(auto e:g[k]){
      if(e.to == par[k])continue;
      head[e.to] = (e.to == g[k][0].to ? head[k]: e.to);
      edges[time] = e;
      dfs_hld(e.to);
    }
    out[k] = time;
  }
  int lca(int p,int q){
    while(1){
      if(in[p] < in[q])swap(p,q);
      if(head[p] == head[q])return q;
      p = par[head[p]];
    }
  }
  vector<pair<int,int>>query_path(int p,int q,bool isEdge){
    int r=lca(p,q);
    vector<pair<int,int>>ret;
    for(int i=0;i<2;i++){
      if(i == 1)swap(p,q);
      while(1){
        if(isEdge&&p==r)break;
        if(head[p]==head[r]){
          ret.emplace_back(in[r]+(isEdge?1:i),in[p]+1);
          break;
        }
        ret.emplace_back(in[head[p]],in[p]+1);
        p = par[head[p]];
      }
    }
    return ret;
  }
  vector<vector<pair<int,int>>>query_order_path(int p,int q,bool isEdge){
	//非可換クエリ用、配列0を順番を反転したデータ構造に、配列1を通常のデータ構造に
    vector<vector<pair<int,int>>>ret(2);
    int r=lca(p,q);
    for(int i=0;i<2;i++){
      if(i == 1)swap(p,q);
      while(1){
        if(isEdge&&p==r)break;
        if(head[p]==head[r]){
          if(i==0) ret[i].emplace_back(n-(in[p]+1),n-(in[r]+(isEdge?1:i)));
          else ret[i].emplace_back(in[r]+(isEdge?1:i),in[p]+1);
          break;
        }
        if(i==0) ret[i].emplace_back(n-(in[p]+1),n-(in[head[p]]));
        else ret[i].emplace_back(in[head[p]],in[p]+1);
        p = par[head[p]];
      }
    }
    reverse(ret[1].begin(), ret[1].end());
    return ret;
  }
  pair<int,int>query_subtree(int p,bool isEdge){
    return make_pair(in[p]+isEdge,out[p]);
  }
  //uのv方向の子 子孫関係は前もって確認すること(in,outを見る)
  int child(int u,int v)const{
    while(1){
      if(head[u]==head[v]){
        v=g[u][0].to;
        break;
      }
      v=head[v];
      if(par[v]==u)break;
      v=par[v];
    }
    return v;
  }
  //uをv方向に一つ進めた頂点
  int move(int u,int v)const{
    assert(u!=v);
    if(in[u]<in[v]&&in[v]<out[u])return child(u,v);
    else return par[u];
  }
  D dist(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
  }
  vector<int>rev_in;
  int climb(int u,int k){
    if(rev_in.empty()){
      rev_in.resize(n);
      for(int i=0;i<n;i++)rev_in[in[i]]=i;
    }
    int nd=max<int>(dep[u]-k, 0);
    while(dep[u]>nd){
      if(dep[head[u]]>nd){
        u=par[head[u]];
      }
      else{
        u=rev_in[in[head[u]]+nd-dep[head[u]]];
      }
    }
    return u;
  }
  int jump(int from,int to, int k){
    int r = lca(from, to);
    int d1 = dep[from] - dep[r];
    int d2 = dep[to] - dep[r];
    if(d1 + d2 < k)return -1;
    else if(k <= d1)return climb(from, k);
    else return climb(to, d1 + d2 - k); 
  }
  template<typename I>
  Graph<T>lca_tree(vector<I>&v){
    auto compare=[&](int x,int y){return in[x]<in[y];};
    sort(v.begin(),v.end(),compare);
    int sz1=v.size();
    for(int i=0;i<sz1-1;i++)v.push_back(lca(v[i],v[i+1]));
    sort(v.begin(),v.end(),compare);
    v.erase(unique(v.begin(),v.end()),v.end());
    int sz2=v.size();
    Graph<T>ret(sz2);
    stack<int>st;
    for(int i=0;i<sz2;i++){
      while(!st.empty()&&out[v[st.top()]]<=in[v[i]])st.pop();
      if(!st.empty()){
        ret[st.top()].emplace_back(i,dep[v[i]]-dep[v[st.top()]]);
        ret[i].emplace_back(st.top(),dep[v[i]]-dep[v[st.top()]]);
      }
      st.push(i);
    }
    return ret;
  }
};
const int VERTEX = 0;
const int HEAVY_LIGHT = -1;
const int LIGHT = -2;
const int HEAVY = -3;
template<typename T>
struct StaticToptree{
  const HLD<T> &hld;
  int count;
  int root;
  vector<int>l,r,p;
  vector<int>aff;
  T edge_identity;
  StaticToptree(const HLD<T> &hld):hld(hld),edge_identity(edge_identity),count(hld.n),l(hld.n*2-1,-1),r(hld.n*2-1,-1),p(hld.n*2-1,-1),aff(hld.n*2-1,VERTEX){
    int hld_root=min_element(hld.in.begin(),hld.in.end())-hld.in.begin();
    root = dfs(hld_root,-1).second;
  }
  //dep,vid
  pair<int,int>dfs(int v,int par){
    vector<int>vs;
    vector<int>dep;
    int now=v,pre=par;
    while(1){
      //vid,eid
      priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
      for(int i=1;i<hld.g[now].size();i++){
        if(hld.g[now][i].to==pre)continue;
        auto [dep, vid] = dfs(hld.g[now][i].to, now);
        pq.emplace(dep,vid);
      }
      while(pq.size()>=2){
        auto [sx,x]=pq.top();pq.pop();
        auto [sy,y]=pq.top();pq.pop();
        int nv=count++;
        aff[nv]=LIGHT;
        l[nv]=x;
        p[x]=nv;
        r[nv]=y;
        p[y]=nv;
        pq.emplace(max(sx,sy)+1,nv);
      }
      int last=now;
      int lastdep=0;
      if(!pq.empty()){
        lastdep=pq.top().first+1;
        auto [sx,x]=pq.top();pq.pop();
        int nv=count++;
        aff[nv]=HEAVY_LIGHT;
        l[nv]=now;
        p[x]=nv;
        r[nv]=x;
        p[now]=nv;
        last=nv;
      }
      vs.push_back(last);
      dep.push_back(lastdep);
      if(hld.g[now].empty()||hld.g[now][0]==pre)break;
      pre=now;
      now=hld.g[now][0];
    }
    vector<int>nvs,ndep;
    auto merge=[&](){
      int rv=nvs.back();nvs.pop_back();
      int lv=nvs.back();nvs.pop_back();
      int rdep=ndep.back();ndep.pop_back();
      int ldep=ndep.back();ndep.pop_back();
      int nv=count++;
      aff[nv]=HEAVY;
      l[nv]=lv,p[lv]=nv;
      r[nv]=rv,p[rv]=nv;
      nvs.push_back(nv);
      ndep.push_back(max(ldep,rdep)+1);
    };
    for(int i=0;i<vs.size();i++){
      int xv=vs[i],x=dep[i];
      ndep.push_back(x);
      nvs.push_back(xv);
      while(1){
        int len=nvs.size();
        if(len>=3&&(ndep[len-3]==ndep[len-2]||ndep[len-3]<=ndep[len-1])){
          int z=ndep[len-1];
          int rem=nvs.back();
          ndep.pop_back();nvs.pop_back();
          merge();
          ndep.push_back(z);nvs.push_back(rem);
        }else if(len>=2&&ndep[len-2]<=ndep[len-1]){
          merge();
        }else{
          break;
        }
      }
    }
    while(nvs.size()>=2)merge();
    return make_pair(ndep[0],nvs[0]);
  }
};

template<typename T,typename V,typename F1,typename F2,typename F3>
struct DynamicReRooting{
  const StaticToptree<T> &t;
  vector<V>seg,ges;
  const F1 &fh;
  const F2 &fl;
  const F3 &fhl;
  const V M1;
  vector<int>path;
  DynamicReRooting(const StaticToptree<T> &t,const F1 &heavy_merge,const F2 &light_merge,const F3 &heavy_light_merge,const V M1):
  t(t),fh(heavy_merge),fl(light_merge),fhl(heavy_light_merge),M1(M1){
    seg.assign(t.aff.size(),M1);
    ges.assign(t.aff.size(),M1);
  }
  void set(int k,V val){
    seg[k]=val;
    ges[k]=val;
  }
  void recalc(int k){
    if(t.aff[k]==LIGHT){
      seg[k]=fl(seg[t.l[k]],seg[t.r[k]]);
    }
    else if(t.aff[k]==HEAVY){
      seg[k]=fh(seg[t.l[k]],seg[t.r[k]]);
      ges[k]=fh(ges[t.r[k]],ges[t.l[k]]);
    }
    else if(t.aff[k]==HEAVY_LIGHT){
      seg[k]=fhl(seg[t.l[k]],seg[t.r[k]]);
      ges[k]=seg[k];
    }
  }
  void build(){
    for(int i=0;i<t.aff.size();i++){
      recalc(i);
    }
  }
  void update(int k,V val){
    seg[k]=val;
    ges[k]=val;
    while(t.p[k]!=-1){
      k=t.p[k];
      recalc(k);
    }
  }
  int root_path(int k){
    int cnt=0;
    while(1){
      if(cnt>=path.size())path.push_back(0);
      path[cnt++]=k;
      if(t.p[k]==-1)break;
      k=t.p[k];
    }
    return cnt;
  }
  //head,tail,light
  tuple<V,V,V>get(int k){
    int m=root_path(k);
    V head=M1,tail=M1,light=M1;
    int hl=-1;
    for(int i=m-1;i>=1;i--){
      if(t.aff[path[i]]==HEAVY){
        if(t.l[path[i]]==path[i-1]){
          tail=fh(seg[t.r[path[i]]],tail);
        }
        else{
          auto lt=ges[t.l[path[i]]];
          head=fh(ges[t.l[path[i]]],head);
        }
      }
      else if(t.aff[path[i]]==HEAVY_LIGHT){
        if(i==1&&k==t.l[path[i]])light=seg[t.r[path[i]]];
        else hl=t.l[path[i]];
      }
      else{
        //LIGHT
        if(t.l[path[i]]==path[i-1]){
          light=fl(seg[t.r[path[i]]],light);
        }
        else{
          light=fl(seg[t.l[path[i]]],light);
        }
      }
      if(hl!=-1&&t.aff[path[i-1]]!=LIGHT){
        head=fhl(seg[hl],fl(light,fl(head,tail)));
        tail=M1;
        light=M1;
        hl=-1;
      }
    }
    return make_tuple(head,tail,light);
  }
  V reroot(int r){
    auto [head,tail,light]=get(r);
    return fhl(seg[r],fl(light,fl(head,tail)));
  }
  V reroot(int r,int k){
    if(r==k)return reroot(r);
    r=t.hld.move(k,r);
    if(r==t.hld.par[k]){
      auto [head,tail,light]=get(k);
      return fhl(seg[k],fl(light,tail));
    }
    else{
      auto [head,tail,light]=get(r);
      return head;
    }
  }
  V prod_root(){
    return seg.back();
  }
  template<typename PF>
  void print(PF printer){
    vector<vector<int>>vst(t.aff.size());
    for(int i=0;i<t.aff.size();i++){
      if(t.aff[i]==VERTEX){
        vst[i].push_back(i);
        cout<<"[VERTEX]: "<<i<<endl;
      }
      else if(t.aff[i]==HEAVY){
        vst[i]=vst[t.l[i]];
        vst[i].insert(vst[i].end(),vst[t.r[i]].begin(),vst[t.r[i]].end());
        cout<<"[HEAVY]: ";for(auto v:vst[i])cout<<v<<" ";cout<<endl;
      }
      else if(t.aff[i]==LIGHT){
        for(auto v:{t.l[i],t.r[i]}){
          if(t.aff[v]==LIGHT)vst[i].insert(vst[i].end(),vst[v].begin(),vst[v].end());
          else vst[i].push_back(vst[v][0]);
        }
        cout<<"[LIGHT]: ";for(auto v:vst[i])cout<<v<<" ";cout<<endl;
      }
      else{
        vst[i].push_back(vst[t.l[i]][0]);
        cout<<"[HL]: "<<vst[i][0]<<" exclude: "<<t.hld.g[vst[i][0]][0].to<<endl;
      }
      printer(seg[i]);
    }
  }
};
using cpx = complex<double>;
const double PI = acos(-1);
vector<cpx> roots = {{0, 0},
                     {1, 0}};

void ensure_capacity(int min_capacity) {
    for (int len = roots.size(); len < min_capacity; len *= 2) {
        for (int i = len >> 1; i < len; i++) {
            roots.emplace_back(roots[i]);
            double angle = 2 * PI * (2 * i + 1 - len) / (len * 2);
            roots.emplace_back(cos(angle), sin(angle));
        }
    }
}

void fft(vector<cpx> &z, bool inverse) {
    int n = z.size();
    assert((n & (n - 1)) == 0);
    ensure_capacity(n);
    for (unsigned i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j >= bit; bit >>= 1)
            j -= bit;
        j += bit;
        if (i < j)
            swap(z[i], z[j]);
    }
    for (int len = 1; len < n; len <<= 1) {
        for (int i = 0; i < n; i += len * 2) {
            for (int j = 0; j < len; j++) {
                cpx root = inverse ? conj(roots[j + len]) : roots[j + len];
                cpx u = z[i + j];
                cpx v = z[i + j + len] * root;
                z[i + j] = u + v;
                z[i + j + len] = u - v;
            }
        }
    }
    if (inverse)
        for (int i = 0; i < n; i++)
            z[i] /= n;
}

vector<int> multiply_bigint(const vector<int> &a, const vector<int> &b, int base) {
    int need = a.size() + b.size();
    int n = 1;
    while (n < need) n <<= 1;
    vector<cpx> p(n);
    for (size_t i = 0; i < n; i++) {
        p[i] = cpx(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
    }
    fft(p, false);
    // a[w[k]] = (p[w[k]] + conj(p[w[n-k]])) / 2
    // b[w[k]] = (p[w[k]] - conj(p[w[n-k]])) / (2*i)
    vector<cpx> ab(n);
    cpx r(0, -0.25);
    for (int i = 0; i < n; i++) {
        int j = (n - i) & (n - 1);
        ab[i] = (p[i] * p[i] - conj(p[j] * p[j])) * r;
    }
    fft(ab, true);
    vector<int> result(need);
    long long carry = 0;
    for (int i = 0; i < need; i++) {
        long long d = (long long) (ab[i].real() + 0.5) + carry;
        carry = d / base;
        result[i] = d % base;
    }
    return result;
}

vector<int> multiply_mod(const vector<int> &a, const vector<int> &b, int m) {
    int need = a.size() + b.size() - 1;
    int n = 1;
    while (n < need) n <<= 1;
    vector<cpx> A(n);
    for (size_t i = 0; i < a.size(); i++) {
        int x = (a[i] % m + m) % m;
        A[i] = cpx(x & ((1 << 15) - 1), x >> 15);
    }
    fft(A, false);

    vector<cpx> B(n);
    for (size_t i = 0; i < b.size(); i++) {
        int x = (b[i] % m + m) % m;
        B[i] = cpx(x & ((1 << 15) - 1), x >> 15);
    }
    fft(B, false);

    vector<cpx> fa(n);
    vector<cpx> fb(n);
    for (int i = 0, j = 0; i < n; i++, j = n - i) {
        cpx a1 = (A[i] + conj(A[j])) * cpx(0.5, 0);
        cpx a2 = (A[i] - conj(A[j])) * cpx(0, -0.5);
        cpx b1 = (B[i] + conj(B[j])) * cpx(0.5, 0);
        cpx b2 = (B[i] - conj(B[j])) * cpx(0, -0.5);
        fa[i] = a1 * b1 + a2 * b2 * cpx(0, 1);
        fb[i] = a1 * b2 + a2 * b1;
    }

    fft(fa, true);
    fft(fb, true);
    vector<int> res(need);
    for (int i = 0; i < need; i++) {
        long long aa = (long long) (fa[i].real() + 0.5);
        long long bb = (long long) (fb[i].real() + 0.5);
        long long cc = (long long) (fa[i].imag() + 0.5);
        res[i] = (aa % m + (bb % m << 15) + (cc % m << 30)) % m;
    }
    return res;
}
constexpr int digits(int base) noexcept {
    return base <= 1 ? 0 : 1 + digits(base / 10);
}
constexpr int base = 1000'000'000;
constexpr int base_digits = digits(base);

constexpr int fft_base = 10'000; // fft_base^2 * n / fft_base_digits <= 10^15 for double
constexpr int fft_base_digits = digits(fft_base);

struct bigint {
    // value == 0 is represented by empty z
    vector<int> z; // digits

    // sign == 1 <==> value >= 0
    // sign == -1 <==> value < 0
    int sign;

    bigint(long long v = 0) {
        *this = v;
    }

    bigint &operator=(long long v) {
        sign = v < 0 ? -1 : 1;
        v *= sign;
        z.clear();
        for (; v > 0; v = v / base)
            z.push_back((int) (v % base));
        return *this;
    }

    bigint(const string &s) {
        read(s);
    }

    bigint &operator+=(const bigint &other) {
        if (sign == other.sign) {
            for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
                if (i == z.size())
                    z.push_back(0);
                z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
                carry = z[i] >= base;
                if (carry)
                    z[i] -= base;
            }
        } else if (other != 0 /* prevent infinite loop */) {
            *this -= -other;
        }
        return *this;
    }

    friend bigint operator+(bigint a, const bigint &b) {
        a += b;
        return a;
    }

    bigint &operator-=(const bigint &other) {
        if (sign == other.sign) {
            if ((sign == 1 && *this >= other) || (sign == -1 && *this <= other)) {
                for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
                    z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
                    carry = z[i] < 0;
                    if (carry)
                        z[i] += base;
                }
                trim();
            } else {
                *this = other - *this;
                this->sign = -this->sign;
            }
        } else {
            *this += -other;
        }
        return *this;
    }

    friend bigint operator-(bigint a, const bigint &b) {
        a -= b;
        return a;
    }

    bigint &operator*=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = 0, carry = 0; i < z.size() || carry; ++i) {
            if (i == z.size())
                z.push_back(0);
            long long cur = (long long) z[i] * v + carry;
            carry = (int) (cur / base);
            z[i] = (int) (cur % base);
        }
        trim();
        return *this;
    }

    bigint operator*(int v) const {
        return bigint(*this) *= v;
    }

    friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
        int norm = base / (b1.z.back() + 1);
        bigint a = a1.abs() * norm;
        bigint b = b1.abs() * norm;
        bigint q, r;
        q.z.resize(a.z.size());

        for (int i = (int) a.z.size() - 1; i >= 0; i--) {
            r *= base;
            r += a.z[i];
            int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
            int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
            int d = (int) (((long long) s1 * base + s2) / b.z.back());
            r -= b * d;
            while (r < 0)
                r += b, --d;
            q.z[i] = d;
        }

        q.sign = a1.sign * b1.sign;
        r.sign = a1.sign;
        q.trim();
        r.trim();
        return {q, r / norm};
    }

    friend bigint sqrt(const bigint &a1) {
        bigint a = a1;
        while (a.z.empty() || a.z.size() % 2 == 1)
            a.z.push_back(0);

        int n = a.z.size();

        int firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
        int norm = base / (firstDigit + 1);
        a *= norm;
        a *= norm;
        while (a.z.empty() || a.z.size() % 2 == 1)
            a.z.push_back(0);

        bigint r = (long long) a.z[n - 1] * base + a.z[n - 2];
        firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
        int q = firstDigit;
        bigint res;

        for (int j = n / 2 - 1; j >= 0; j--) {
            for (;; --q) {
                bigint r1 = (r - (res * 2 * base + q) * q) * base * base +
                            (j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
                if (r1 >= 0) {
                    r = r1;
                    break;
                }
            }
            res *= base;
            res += q;

            if (j > 0) {
                int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
                int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
                int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
                q = (int) (((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2));
            }
        }

        res.trim();
        return res / norm;
    }

    bigint operator/(const bigint &v) const {
        return divmod(*this, v).first;
    }

    bigint operator%(const bigint &v) const {
        return divmod(*this, v).second;
    }

    bigint &operator/=(int v) {
        if (v < 0)
            sign = -sign, v = -v;
        for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {
            long long cur = z[i] + rem * (long long) base;
            z[i] = (int) (cur / v);
            rem = (int) (cur % v);
        }
        trim();
        return *this;
    }

    bigint operator/(int v) const {
        return bigint(*this) /= v;
    }

    int operator%(int v) const {
        if (v < 0)
            v = -v;
        int m = 0;
        for (int i = (int) z.size() - 1; i >= 0; --i)
            m = (int) ((z[i] + m * (long long) base) % v);
        return m * sign;
    }

    bigint &operator*=(const bigint &v) {
        *this = *this * v;
        return *this;
    }

    bigint &operator/=(const bigint &v) {
        *this = *this / v;
        return *this;
    }

    bigint &operator%=(const bigint &v) {
        *this = *this % v;
        return *this;
    }

    bool operator<(const bigint &v) const {
        if (sign != v.sign)
            return sign < v.sign;
        if (z.size() != v.z.size())
            return z.size() * sign < v.z.size() * v.sign;
        for (int i = (int) z.size() - 1; i >= 0; i--)
            if (z[i] != v.z[i])
                return z[i] * sign < v.z[i] * sign;
        return false;
    }

    bool operator>(const bigint &v) const {
        return v < *this;
    }

    bool operator<=(const bigint &v) const {
        return !(v < *this);
    }

    bool operator>=(const bigint &v) const {
        return !(*this < v);
    }

    bool operator==(const bigint &v) const {
        return !(*this < v) && !(v < *this);
    }

    bool operator!=(const bigint &v) const {
        return *this < v || v < *this;
    }

    void trim() {
        while (!z.empty() && z.back() == 0)
            z.pop_back();
        if (z.empty())
            sign = 1;
    }

    bool isZero() const {
        return z.empty();
    }

    friend bigint operator-(bigint v) {
        if (!v.z.empty())
            v.sign = -v.sign;
        return v;
    }

    bigint abs() const {
        return sign == 1 ? *this : -*this;
    }

    long long longValue() const {
        long long res = 0;
        for (int i = (int) z.size() - 1; i >= 0; i--)
            res = res * base + z[i];
        return res * sign;
    }

    friend bigint gcd(const bigint &a, const bigint &b) {
        return b.isZero() ? a : gcd(b, a % b);
    }

    friend bigint lcm(const bigint &a, const bigint &b) {
        return a / gcd(a, b) * b;
    }

    void read(const string &s) {
        sign = 1;
        z.clear();
        int pos = 0;
        while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) {
            if (s[pos] == '-')
                sign = -sign;
            ++pos;
        }
        for (int i = (int) s.size() - 1; i >= pos; i -= base_digits) {
            int x = 0;
            for (int j = max(pos, i - base_digits + 1); j <= i; j++)
                x = x * 10 + s[j] - '0';
            z.push_back(x);
        }
        trim();
    }

    friend istream &operator>>(istream &stream, bigint &v) {
        string s;
        stream >> s;
        v.read(s);
        return stream;
    }

    friend ostream &operator<<(ostream &stream, const bigint &v) {
        if (v.sign == -1)
            stream << '-';
        stream << (v.z.empty() ? 0 : v.z.back());
        for (int i = (int) v.z.size() - 2; i >= 0; --i)
            stream << setw(base_digits) << setfill('0') << v.z[i];
        return stream;
    }

    static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
        vector<long long> p(max(old_digits, new_digits) + 1);
        p[0] = 1;
        for (int i = 1; i < p.size(); i++)
            p[i] = p[i - 1] * 10;
        vector<int> res;
        long long cur = 0;
        int cur_digits = 0;
        for (int v : a) {
            cur += v * p[cur_digits];
            cur_digits += old_digits;
            while (cur_digits >= new_digits) {
                res.push_back(int(cur % p[new_digits]));
                cur /= p[new_digits];
                cur_digits -= new_digits;
            }
        }
        res.push_back((int) cur);
        while (!res.empty() && res.back() == 0)
            res.pop_back();
        return res;
    }

    bigint operator*(const bigint &v) const {
        if (min(z.size(), v.z.size()) < 150)
            return mul_simple(v);
        bigint res;
        res.sign = sign * v.sign;
        res.z = multiply_bigint(convert_base(z, base_digits, fft_base_digits),
                                convert_base(v.z, base_digits, fft_base_digits), fft_base);
        res.z = convert_base(res.z, fft_base_digits, base_digits);
        res.trim();
        return res;
    }

    bigint mul_simple(const bigint &v) const {
        bigint res;
        res.sign = sign * v.sign;
        res.z.resize(z.size() + v.z.size());
        for (int i = 0; i < z.size(); ++i)
            if (z[i])
                for (int j = 0, carry = 0; j < v.z.size() || carry; ++j) {
                    long long cur = res.z[i + j] + (long long) z[i] * (j < v.z.size() ? v.z[j] : 0) + carry;
                    carry = (int) (cur / base);
                    res.z[i + j] = (int) (cur % base);
                }
        res.trim();
        return res;
    }
};

mt19937 rng(1);

bigint random_bigint(int n) {
    string s;
    for (int i = 0; i < n; i++) {
        s += uniform_int_distribution<int>('0', '9')(rng);
    }
    return bigint(s);
}
vector<string>val;
Graph<int>tree;

using State = string::iterator;
template<typename T>
struct Parsing{
  Parsing(){};
  T solve(string &s){
    State itr = s.begin();
    return expr(itr);
  }
  T expr(State &itr){
    T now = term(itr);
    while(1){
      if(*itr == '+' || *itr == '-'){
        char sig=*itr;
        T nxt = term(++itr);
        int idx=tree.size();
        tree.EB();
        tree[idx].EB(now);
        tree[idx].EB(nxt);
        val.PB(string(1,sig));
        now=idx;
      }
      else break;
    }
    return now;
  }
  T term(State &itr){
    T now = fact(itr);
    while(1){
      if(*itr == '*'){
        T nxt = fact(++itr);
        int idx = tree.size();
        tree.emplace_back();
        tree[idx].emplace_back(now);
        tree[idx].emplace_back(nxt);
        val.PB("*");
        now=idx;
      }
      else break;
    }
    return now;
  }
  T fact(State &itr){
    if(*itr=='-'||isdigit(*itr))return number(itr);
    assert(*itr == '(');
    itr++;
    T val = expr(itr);
    assert(*itr == ')');
    itr++;
    return val;
  }
  T number(State &itr){
    string num;
    while(*itr=='-'){
      num += *itr;
      itr++;
    }
    while(isdigit(*itr)){
      num += *itr;
      itr++;
    }
    int idx=tree.size();
    tree.emplace_back();
    val.push_back(num);
    return idx;
  }
};
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  ll n;cin>>n;
  string s;cin>>s;
  Parsing<int>parse;
  int root=parse.solve(s);
  auto pre_tree=tree;
  HLD hld(tree,root);
  StaticToptree st(hld);
  OUT(tree,val);
  OUT(root);
  auto dfs=[&](auto &&f,int k)->pair<bigint,bigint>{
    {}
    auto af=st.aff[k];
    if(af==VERTEX){
      if(val[k]=="+"||val[k]=="-"||val[k]=="*")return MP(-1,-1);
      else return MP(1,val[k]);
    }
    auto lf=f(f,st.l[k]);
    auto rf=f(f,st.r[k]);
    OUT(k,lf,rf,st.l[k],st.r[k]);
    if(af==LIGHT){
      assert(false);
    }
    if(af==HEAVY_LIGHT){
      if(val[st.l[k]]=="+"){
        return MP(1,rf.se);
      }
      else if(val[st.l[k]]=="-"){
        int rr=st.l[k];
        if(pre_tree[rr][0]==tree[rr][0])return MP(1,-rf.se);
        else return MP(-1,rf.se);
      }
      else{
        assert(val[st.l[k]]=="*");
        return MP(rf.se,0);
      }
    }
    if(af==HEAVY){
      return MP(lf.fi*rf.fi,lf.fi*rf.se+lf.se);
    }
  };
  auto ret=dfs(dfs,st.root);
  cout<<ret.se<<endl;
  return 0;
}
0