Submission #974854

#	Time	Username	Problem	Language	Result	Execution time	Memory
974854		Angus_Yeung	Homework (CEOI22_homework)	C++17	100 / 100	76 ms	39956 KiB

Main

#include <bits/stdc++.h>
#define l first
#define r second
#define pii pair<ll, ll>
typedef long long ll;
const ll MOD = 1000000007LL;
const ll INF = 1e15;
using namespace std;

ll n;
pii a, b;
string s;
stack<pii> stk;

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> s;
	for (int i = 0; i < s.length(); i++) n += (s[i] == '?');
	
	for (int i = s.length()-1; i >= 0; i--) {
		if (s[i] == ')') {
			stk.push({1, n});
		} else if (s[i] == '?') {
			stk.push({1, n});
		} else if (s[i] == 'a') {
			a = stk.top(); stk.pop();
			b = stk.top(); stk.pop();
			stk.top() = {a.l+b.l, max(a.r, b.r)};
		} else if (s[i] == 'i') {
			a = stk.top(); stk.pop();
			b = stk.top(); stk.pop();
			stk.top() = {min(a.l, b.l), n-(n-a.r)-(n-b.r)-1};
		}
	}
	
	cout << min(n, max(0LL, stk.top().r-stk.top().l+1)) << "\n";
	
	return 0;
}
/*



*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 0; i < s.length(); i++) n += (s[i] == '?');
      |                  ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34