Submission #994391

#	Time	Username	Problem	Language	Result	Execution time	Memory
994391		biank	Homework (CEOI22_homework)	C++14	53 / 100	24 ms	39128 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())
#define all(x) begin(x),end(x)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dbg(x) cerr<<#x<<": "<<x<<endl

#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> ii;

const int MAXN=1e6+20;

string s;
int l[MAXN],r[MAXN];

struct Val{
    int l,r,sz;
    int cant(){return r-l+1;}
};

Val solve(int u){
    if(s[u]=='?') return {1,1,1};
    Val lch=solve(l[u]);
    Val rch=solve(r[u]);
    Val res;
    res.sz=lch.sz+rch.sz;
    if(s[u]=='n'){//min
        res.l=min(lch.l,rch.l);
        res.r=lch.r+rch.r-1;
    }else if(s[u]=='x'){//max
        res.l=lch.l+rch.l;
        res.r=max(rch.sz+lch.r,lch.sz+rch.r);
    }else assert(false);
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> s;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    stack<int> st;
    forn(i,sz(s)){
        if(s[i]=='n'||s[i]== 'x'||s[i]=='?'){
            st.push(i);
        }else if(s[i]==','||s[i]==')'){
            int j=st.top(); st.pop();
            if (l[st.top()] == -1) l[st.top()] = j;
            else r[st.top()] = j;
        }
    }
    cout<<solve(st.top()).cant()<<'\n';
    
    return 0;
}

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