Submission #726537

#TimeUsernameProblemLanguageResultExecution timeMemory
726537viwlesxqHomework (CEOI22_homework)C++17
53 / 100
1036 ms14112 KiB
#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef string str;

int n;
str s;

pair <int, int> get_range(int i) {
  if (s[i] == '?') {
    return {1, n};
  } else if (s[i + 2] == 'x') {
    int comma, cnt = 0;
    for (int j = i + 4; ; ++j) {
      if (s[j] == ',' && !cnt) {
        comma = j;
        break;
      }
      if (s[j] == '(') {
        ++cnt;
      } 
      if (s[j] == ')') {
        --cnt;
      }
    }
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma + 1);
    range.second = max(range_left.second, range_right.second);
    range.first = range_left.first + range_right.first;
    return range;
  } else {
    int comma, cnt = 0;
    for (int j = i + 4; ; ++j) {
      if (s[j] == ',' && !cnt) {
        comma = j;
        break;
      }
      if (s[j] == '(') {
        ++cnt;
      } 
      if (s[j] == ')') {
        --cnt;
      }
    }
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma + 1);
    range.second = range_left.second + range_right.second - n - 1;
    range.first = min(range_left.first, range_right.first);
    return range;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> s;
  n = count(s.begin(), s.end(), '?');
  pair <int, int> range = get_range(0);
  cout << range.second - range.first + 1;
}
#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...