This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 6e6 + 10;
struct node {
int a, l, r;
node() : a(1), l(0), r(0) {}
node(int a, int l, int r) : a(a), l(l), r(r) {}
};
node min(node a, node b) {
return node(a.a + b.a, min(a.l, b.l), a.r + b.r + 1);
}
node max(node a, node b) {
return node(a.a + b.a, a.l + b.l + 1, min(a.r, b.r));
}
int n;
char C[N];
int ind = 0;
node dfs(int i) {
if(C[i] == '?') {
ind = i;
return node();
} else if(C[i + 2] == 'x') {
node a = dfs(i + 4);
node b = dfs(ind + 2);
ind += 1;
// printf("max %d %d %d %d %d %d\n", a.a, a.l, a.r, b.a, b.l, b.r);
return max(a, b);
}
node a = dfs(i + 4);
node b = dfs(ind + 2);
ind += 1;
// printf("min %d %d %d %d %d %d\n", a.a, a.l, a.r, b.a, b.l, b.r);
return min(a, b);
}
int main() {
scanf("%s%n ", C, &n);
node res = dfs(0);
printf("%d\n", res.a - res.l - res.r);
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%s%n ", C, &n);
| ~~~~~^~~~~~~~~~~~~~~~
# | 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... |