#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 4e6 + 10, inf = 1e15;
struct segment {
pair <int, int> seg[maxn << 2];
void build (int i, int L, int R, vector <int> &a){
if (L == R){
seg[i] = {a[L], L};
return;
}
int mid = (R + L) >> 1;
build(i << 1, L, mid, a);
build((i << 1) ^ 1, mid + 1, R, a);
seg[i] = min(seg[i << 1], seg[(i << 1) ^ 1]);
}
pair <int, int> get (int i, int L, int R, int l, int r){
if (L > r || R < l) return {inf, inf};
if (L >= l && R <= r) return seg[i];
int mid = (R + L) >> 1;
return min(get(i << 1, L, mid, l, r), get((i << 1) ^ 1, mid + 1, R, l, r));
}
}seg;
string s;
void read (){
cin >> s;
}
bool b[maxn];
vector <int> a;
void MakeA (){
for (int i = 0; i < s.size(); i++){
if (s[i] == '('){
a.push_back(1);
if (s[i - 1] == 'n')
b[a.size() - 1] = 0;
else if (s[i - 1] == 'x')
b[a.size() - 1] = 1;
}
else if (s[i] == ')')
a.push_back(-1);
else if (s[i] == '?'){
a.push_back(1);
a.push_back(-1);
}
}
for (int i = 1; i < a.size(); i++)
a[i] += a[i - 1];
}
vector <int> adj[maxn];
int MakeT (int l, int r){
if (r - l == 1) return l;
int j = seg.get(1, 0, a.size() - 1, l + 1, r - 1).second;
int lc = MakeT(l + 1, j);
int rc = MakeT(j + 1, r - 1);
adj[l].push_back(lc);
adj[l].push_back(rc);
return l;
}
struct str {
int l, r, s;
};
str dfs (int v = 0){
if (adj[v].size() == 0) return {1, 1, 1};
auto [l1, r1, s1] = dfs(adj[v][0]);
auto [l2, r2, s2] = dfs(adj[v][1]);
if (b[v] == 0) return {min(l1, l2), r1 + r2 - 1, s1 + s2};
return {l1 + l2, max(r1 + s2, r2 + s1), s1 + s2};
}
int ans = 0;
void solve (){
MakeA();
seg.build(1, 0, a.size() - 1, a);
MakeT(0, a.size() - 1);
auto [l, r, s] = dfs();
ans = r - l + 1;
}
void print (){
cout << ans;
}
int32_t main (){
ios_base::sync_with_stdio(0), cin.tie(0);
read();
solve();
print();
}
# | 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... |