Submission #1127707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127707		pemguimn	Homework (CEOI22_homework)	C++17	100 / 100	316 ms	222600 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int S = 1e7 + 5, N = 2e6 + 5;

string s; int cntq;
int id = 0, mp[S];
vector<int> adj[N];
int t[N], l[N], r[N], sz[N];


int cntmn = 0, cntmx = 0, cntleaf = 0;
int dnc(int l, int r){
    ++id; int cur = id;
    if(r - l == 0) t[id] = 0, cntleaf++;
    else{
        if(s[l + 1] == 'i') t[cur] = -1, cntmn++;
        else t[cur] = 1, cntmx++;
        adj[cur].push_back(dnc(l + 4, (s[l + 4] == '?' ? l + 4 : mp[l + 7])));
        adj[cur].push_back(dnc((s[r - 1] == '?' ? mp[r - 1] : mp[r - 1] - 3), r - 1));
    }
    return cur;
}

namespace full{
    void dfs(int i){
        if(adj[i].size() == 0) {
          sz[i] = 1, l[i] = 1, r[i] = 1;
        } else {
            int u = adj[i][0], v = adj[i][1];
            dfs(u), dfs(v);
            sz[i] = sz[u] + sz[v];
            if(t[i] == -1)
                r[i] = sz[i] - ((sz[u] - r[u]) + (sz[v] - r[v]) + 1), l[i] = min(l[u], l[v]);
            else
                l[i] = l[u] + l[v], r[i] = sz[i] - min(sz[u] - r[u], sz[v] - r[v]);
        }
    }
    void solve(){
        dfs(1);
        cout << r[1] - l[1] + 1 << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;

    stack<int> st;
    for(int i = 0; i < s.size(); i++) mp[i] = i;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '(') st.push(i);
        else if(s[i] == ')') mp[st.top()] = i, mp[i] = st.top(), st.pop();
    }
    dnc(0, s.size() - 1);
    full::solve();
    return 0;
}

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