Submission #674529

#	Time	Username	Problem	Language	Result	Execution time	Memory
674529		esomer	Homework (CEOI22_homework)	C++17	100 / 100	449 ms	280132 KiB

Main

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;
const int maxN = 3000000;

int N;
set<int> closing[maxN];
string s; 

pair<int, int> calc(int l, int r, int depth){
	if(l == r){return {1, 1};}
	int coma;
	if(s[l + 4] == '?') coma = l + 5;
	else{
		coma = *closing[depth + 2].lower_bound(l); coma++;
	}
	pair<int, int> f = calc(l + 4, coma - 1, depth + 1);
	pair<int, int> st = calc(coma + 1, r - 1, depth + 1);
	if(s[l + 1] == 'i'){
		return {f.first + st.first, min(f.second, st.second)};
	}else{
		return {min(f.first, st.first), f.second + st.second};
	}
}

void solve(){
	cin >> s;
	int n = s.size();
	int curr = 0;
	N = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == '?') N++;
		else if(s[i] == '('){
			curr++;
		}else if(s[i] == ')'){
			closing[curr].insert(i);
			curr--;
		}
	}
	pair<int, int> ans = calc(0, n - 1, 0);
	ans.first = N - ans.first + 1;
	cout << ans.first - ans.second + 1 << endl;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

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