Submission #798173

#	Time	Username	Problem	Language	Result	Execution time	Memory
798173		IvanJ	Homework (CEOI22_homework)	C++17	100 / 100	262 ms	162756 KiB

Main

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e6 + 5;

int sz;
string s;
int type[maxn];
int l[maxn], r[maxn];
int L[maxn], R[maxn];
vector<int> adj[maxn];

void solve(int x) {
	if(adj[x].size() == 0) {
		l[x] = r[x] = L[x] = R[x] = 1;
		return;
	} 
	
	int y = adj[x][0], z = adj[x][1];
	solve(y), solve(z);
	L[x] = 1, R[x] = R[y] + R[z];
	
	if(type[x] == 0) {
		l[x] = min(l[y], l[z]);
		r[x] = r[y] + r[z] - 1;
	}
	if(type[x] == 1) {
		l[x] = l[y] + l[z];
		r[x] = max(r[y] + R[z], r[z] + R[y]);
	}
}

int main() {
	cin >> s;
	sz = (int)s.size();
	int idx = 0;
	vector<int> st;
	for(int i = sz - 1;i >= 0;i--) {
		if(s[i] == '?') st.pb(idx++);
		if(s[i] == 'i' || s[i] == 'a') {
			type[idx] = (s[i] == 'a');
			adj[idx].pb(st.back()), st.pop_back();
			adj[idx].pb(st.back()), st.pop_back();
			st.pb(idx++);
		}
	}
	
	idx--;
	solve(idx);
	printf("%d\n", r[idx] - l[idx] + 1);
	return 0;
}

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