Submission #1249869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249869		sinatbtfard	Homework (CEOI22_homework)	C++20	100 / 100	585 ms	438012 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 4e6 + 10, inf = 1e15;

struct segment {
	pair <int, int> seg[maxn << 2];
	void build (int i, int L, int R, vector <int> &a){
		if (L == R){
			seg[i] = {a[L], L};
			return;
		}
		int mid = (R + L) >> 1;
		build(i << 1, L, mid, a);
		build((i << 1) ^ 1, mid + 1, R, a);
		seg[i] = min(seg[i << 1], seg[(i << 1) ^ 1]);
	}
	pair <int, int> get (int i, int L, int R, int l, int r){
		if (L > r || R < l) return {inf, inf};
		if (L >= l && R <= r) return seg[i];
		int mid = (R + L) >> 1;
		return min(get(i << 1, L, mid, l, r), get((i << 1) ^ 1, mid + 1, R, l, r));
	}
}seg;

string s;

void read (){
	cin >> s;
}

bool b[maxn];
vector <int> a;

void MakeA (){
	for (int i = 0; i < s.size(); i++){
		if (s[i] == '('){
			a.push_back(1);
			if (s[i - 1] == 'n')
				b[a.size() - 1] = 0;
			else if (s[i - 1] == 'x')
				b[a.size() - 1] = 1;
		}
		else if (s[i] == ')')
			a.push_back(-1);
		else if (s[i] == '?'){
			a.push_back(1);
			a.push_back(-1);
		}
	}
	for (int i = 1; i < a.size(); i++)
		a[i] += a[i - 1];
}

vector <int> adj[maxn];

int MakeT (int l, int r){
	if (r - l == 1) return l;
	int j = seg.get(1, 0, a.size() - 1, l + 1, r - 1).second;
	int lc = MakeT(l + 1, j);
	int rc = MakeT(j + 1, r - 1);
	adj[l].push_back(lc);
	adj[l].push_back(rc);
	return l;
}

struct str {
	int l, r, s;
};

str dfs (int v = 0){
	if (adj[v].size() == 0) return {1, 1, 1};
	auto [l1, r1, s1] = dfs(adj[v][0]);
	auto [l2, r2, s2] = dfs(adj[v][1]);
	if (b[v] == 0) return {min(l1, l2), r1 + r2 - 1, s1 + s2};
	return {l1 + l2, max(r1 + s2, r2 + s1), s1 + s2};
}

int ans = 0;

void solve (){
	MakeA();
	seg.build(1, 0, a.size() - 1, a);
	MakeT(0, a.size() - 1);
	auto [l, r, s] = dfs();
	ans = r - l + 1;
}

void print (){
	cout << ans;
}

int32_t main (){
	ios_base::sync_with_stdio(0), cin.tie(0);
	read();
	solve();
	print();
}

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