Submission #726538

#TimeUsernameProblemLanguageResultExecution timeMemory
726538viwlesxqHomework (CEOI22_homework)C++17
100 / 100
85 ms37712 KiB
#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef string str;

int n, commas_gone;
str s;
vector <int> comma;

pair <int, int> get_range(int i) {
  if (s[i] == '?') {
    return {1, n};
  } else if (s[i + 2] == 'x') {
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma[commas_gone++] + 1);
    range.second = max(range_left.second, range_right.second);
    range.first = range_left.first + range_right.first;
    return range;
  } else {
    pair <int, int> range_left = get_range(i + 4), range;
    pair <int, int> range_right = get_range(comma[commas_gone++] + 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;
  for (int i = 0; i < (int)s.size(); ++i) {
    if (s[i] == ',') {
      comma.push_back(i);
    }
  }
  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...