#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib>
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int mod=998244353,mxn=1e6+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
int sz[mxn+10];
int st[mxn+10],ed[mxn+10],type[mxn+10];
pii child[mxn+10];
string a;
pii solve(int id){
if(a[id]=='?'){
sz[id]=1;
return {1,1};
}
pii vl,vr;
vl=solve(child[id].f),sz[id]+=sz[child[id].f];
vr=solve(child[id].s),sz[id]+=sz[child[id].s];
pii re;
if(type[id])re={min(vl.f,vr.f),vr.s+vl.s-1};
else re= {vl.f+vr.f,max(vl.s+sz[child[id].s],vr.s+sz[child[id].f])};
return re;
}
int32_t main(){
fastio
cin>>a;
if(a=="?")return cout<<1,0;
stack<int>st;
for(int i=0;i<a.size();i++)child[i]={-1,-1};
for(int i=0;i<a.size();i++){
sz[i]=0;
if(a[i]=='('){
type[i]=(a[i-1]=='n');
st.push(i);
}
else if(a[i]==')'){
int x=st.top();
ed[x]=i;
st.pop();
if(st.empty())continue;
if(child[st.top()].f==-1)child[st.top()].f=x;
else child[st.top()].s=x;
}
else if(a[i]=='?'){
if(child[st.top()].f==-1)child[st.top()].f=i;
else child[st.top()].s=i;
}
}
pii ans=solve(3);
cout<<ans.s-ans.f+1;
return 0;
}
/*
keep range l,r->value thats optainable in subtree
l being the min number of number < x needed to be used
and r being the max
merging-{
min node{
nl=min(l1,l2)-> push value of every node of the other subtree up
nr=(r1+r2-1)->push 1 at the bottom of the other except 1
}
max node{
nl=l1+l2->push 1 at bottom
nr=r1+subsz2 or r2+subsz1 ->taking everything and shift it
}
}
*/
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:62:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0;i<a.size();i++)child[i]={-1,-1};
| ~^~~~~~~~~
Main.cpp:63:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6612 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
1 ms |
6488 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6608 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
1 ms |
6492 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6488 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
1 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6612 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6612 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
1 ms |
6488 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6608 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
1 ms |
6492 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6488 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
1 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6612 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6608 KB |
Output is correct |
33 |
Correct |
1 ms |
6488 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Correct |
1 ms |
6620 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
1 ms |
6488 KB |
Output is correct |
38 |
Correct |
1 ms |
6492 KB |
Output is correct |
39 |
Correct |
1 ms |
6492 KB |
Output is correct |
40 |
Correct |
1 ms |
6492 KB |
Output is correct |
41 |
Correct |
1 ms |
6492 KB |
Output is correct |
42 |
Correct |
1 ms |
6492 KB |
Output is correct |
43 |
Correct |
1 ms |
6492 KB |
Output is correct |
44 |
Correct |
1 ms |
6492 KB |
Output is correct |
45 |
Correct |
1 ms |
6492 KB |
Output is correct |
46 |
Correct |
1 ms |
6492 KB |
Output is correct |
47 |
Correct |
1 ms |
6492 KB |
Output is correct |
48 |
Correct |
1 ms |
6620 KB |
Output is correct |
49 |
Correct |
1 ms |
6608 KB |
Output is correct |
50 |
Correct |
1 ms |
6492 KB |
Output is correct |
51 |
Correct |
1 ms |
6492 KB |
Output is correct |
52 |
Correct |
1 ms |
6492 KB |
Output is correct |
53 |
Correct |
1 ms |
6492 KB |
Output is correct |
54 |
Correct |
1 ms |
6492 KB |
Output is correct |
55 |
Correct |
1 ms |
6488 KB |
Output is correct |
56 |
Correct |
1 ms |
6492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
67 ms |
116780 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6612 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
1 ms |
6488 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6608 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
1 ms |
6492 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6488 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
1 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6612 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6608 KB |
Output is correct |
33 |
Correct |
1 ms |
6488 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Correct |
1 ms |
6620 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
1 ms |
6488 KB |
Output is correct |
38 |
Correct |
1 ms |
6492 KB |
Output is correct |
39 |
Correct |
1 ms |
6492 KB |
Output is correct |
40 |
Correct |
1 ms |
6492 KB |
Output is correct |
41 |
Correct |
1 ms |
6492 KB |
Output is correct |
42 |
Correct |
1 ms |
6492 KB |
Output is correct |
43 |
Correct |
1 ms |
6492 KB |
Output is correct |
44 |
Correct |
1 ms |
6492 KB |
Output is correct |
45 |
Correct |
1 ms |
6492 KB |
Output is correct |
46 |
Correct |
1 ms |
6492 KB |
Output is correct |
47 |
Correct |
1 ms |
6492 KB |
Output is correct |
48 |
Correct |
1 ms |
6620 KB |
Output is correct |
49 |
Correct |
1 ms |
6608 KB |
Output is correct |
50 |
Correct |
1 ms |
6492 KB |
Output is correct |
51 |
Correct |
1 ms |
6492 KB |
Output is correct |
52 |
Correct |
1 ms |
6492 KB |
Output is correct |
53 |
Correct |
1 ms |
6492 KB |
Output is correct |
54 |
Correct |
1 ms |
6492 KB |
Output is correct |
55 |
Correct |
1 ms |
6488 KB |
Output is correct |
56 |
Correct |
1 ms |
6492 KB |
Output is correct |
57 |
Correct |
1 ms |
8808 KB |
Output is correct |
58 |
Correct |
1 ms |
8808 KB |
Output is correct |
59 |
Correct |
2 ms |
8808 KB |
Output is correct |
60 |
Correct |
2 ms |
8808 KB |
Output is correct |
61 |
Correct |
1 ms |
8808 KB |
Output is correct |
62 |
Correct |
1 ms |
8660 KB |
Output is correct |
63 |
Correct |
1 ms |
8796 KB |
Output is correct |
64 |
Correct |
2 ms |
8792 KB |
Output is correct |
65 |
Correct |
1 ms |
8796 KB |
Output is correct |
66 |
Correct |
2 ms |
8796 KB |
Output is correct |
67 |
Correct |
1 ms |
8948 KB |
Output is correct |
68 |
Correct |
2 ms |
8796 KB |
Output is correct |
69 |
Correct |
2 ms |
8656 KB |
Output is correct |
70 |
Correct |
2 ms |
8796 KB |
Output is correct |
71 |
Correct |
2 ms |
8540 KB |
Output is correct |
72 |
Correct |
2 ms |
8796 KB |
Output is correct |
73 |
Correct |
1 ms |
8796 KB |
Output is correct |
74 |
Correct |
1 ms |
8796 KB |
Output is correct |
75 |
Correct |
1 ms |
8796 KB |
Output is correct |
76 |
Correct |
2 ms |
8796 KB |
Output is correct |
77 |
Correct |
1 ms |
8796 KB |
Output is correct |
78 |
Correct |
1 ms |
8540 KB |
Output is correct |
79 |
Correct |
1 ms |
8796 KB |
Output is correct |
80 |
Correct |
1 ms |
8796 KB |
Output is correct |
81 |
Correct |
1 ms |
8796 KB |
Output is correct |
82 |
Correct |
1 ms |
8792 KB |
Output is correct |
83 |
Correct |
1 ms |
8540 KB |
Output is correct |
84 |
Correct |
2 ms |
8652 KB |
Output is correct |
85 |
Correct |
1 ms |
8536 KB |
Output is correct |
86 |
Correct |
1 ms |
6612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6612 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
1 ms |
6488 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6488 KB |
Output is correct |
11 |
Correct |
1 ms |
6488 KB |
Output is correct |
12 |
Correct |
1 ms |
6492 KB |
Output is correct |
13 |
Correct |
1 ms |
6492 KB |
Output is correct |
14 |
Correct |
1 ms |
6608 KB |
Output is correct |
15 |
Correct |
2 ms |
6492 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
1 ms |
6492 KB |
Output is correct |
19 |
Correct |
1 ms |
6492 KB |
Output is correct |
20 |
Correct |
1 ms |
6492 KB |
Output is correct |
21 |
Correct |
1 ms |
6492 KB |
Output is correct |
22 |
Correct |
1 ms |
6488 KB |
Output is correct |
23 |
Correct |
1 ms |
6492 KB |
Output is correct |
24 |
Correct |
1 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6612 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
1 ms |
6492 KB |
Output is correct |
30 |
Correct |
1 ms |
6492 KB |
Output is correct |
31 |
Correct |
1 ms |
6492 KB |
Output is correct |
32 |
Correct |
1 ms |
6608 KB |
Output is correct |
33 |
Correct |
1 ms |
6488 KB |
Output is correct |
34 |
Correct |
1 ms |
6492 KB |
Output is correct |
35 |
Correct |
1 ms |
6620 KB |
Output is correct |
36 |
Correct |
1 ms |
6492 KB |
Output is correct |
37 |
Correct |
1 ms |
6488 KB |
Output is correct |
38 |
Correct |
1 ms |
6492 KB |
Output is correct |
39 |
Correct |
1 ms |
6492 KB |
Output is correct |
40 |
Correct |
1 ms |
6492 KB |
Output is correct |
41 |
Correct |
1 ms |
6492 KB |
Output is correct |
42 |
Correct |
1 ms |
6492 KB |
Output is correct |
43 |
Correct |
1 ms |
6492 KB |
Output is correct |
44 |
Correct |
1 ms |
6492 KB |
Output is correct |
45 |
Correct |
1 ms |
6492 KB |
Output is correct |
46 |
Correct |
1 ms |
6492 KB |
Output is correct |
47 |
Correct |
1 ms |
6492 KB |
Output is correct |
48 |
Correct |
1 ms |
6620 KB |
Output is correct |
49 |
Correct |
1 ms |
6608 KB |
Output is correct |
50 |
Correct |
1 ms |
6492 KB |
Output is correct |
51 |
Correct |
1 ms |
6492 KB |
Output is correct |
52 |
Correct |
1 ms |
6492 KB |
Output is correct |
53 |
Correct |
1 ms |
6492 KB |
Output is correct |
54 |
Correct |
1 ms |
6492 KB |
Output is correct |
55 |
Correct |
1 ms |
6488 KB |
Output is correct |
56 |
Correct |
1 ms |
6492 KB |
Output is correct |
57 |
Runtime error |
67 ms |
116780 KB |
Execution killed with signal 11 |
58 |
Halted |
0 ms |
0 KB |
- |