Submission #831762

#	Time	Username	Problem	Language	Result	Execution time	Memory
831762		QwertyPi	Homework (CEOI22_homework)	C++14	100 / 100	235 ms	101420 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6 + 11;
const int INF = 1 << 30;
int L = INF, R = -INF;
int l[MAXN], r[MAXN], t[MAXN];

struct range{
    int x00, x01, x10, x11;
};

range sz[MAXN];
bool ok[MAXN];
bool is_leaf(int v){
    return l[v] == 0 && r[v] == 0;
}

void dfs(int v){
    if(is_leaf(v)){
        sz[v] = {0, 0, 1, 1};
    }else{
        dfs(l[v]); dfs(r[v]);
        if(t[v] == 1){
            sz[v].x00 = sz[l[v]].x00 + sz[r[v]].x00;
            sz[v].x01 = sz[l[v]].x01 + sz[r[v]].x01;
            sz[v].x10 = min(sz[l[v]].x10 + sz[r[v]].x00, sz[l[v]].x00 + sz[r[v]].x10);
            sz[v].x11 = sz[l[v]].x11 + sz[r[v]].x11;
        }else{
            sz[v].x00 = sz[l[v]].x00 + sz[r[v]].x00;
            sz[v].x01 = max(sz[l[v]].x01 + sz[r[v]].x11, sz[l[v]].x11 + sz[r[v]].x01);
            sz[v].x10 = sz[l[v]].x10 + sz[r[v]].x10;
            sz[v].x11 = sz[l[v]].x11 + sz[r[v]].x11;
        }
    }
}

void dfs2(int v, int vl = 0, int vr = 0){
    if(is_leaf(v)){
        L = min(L, vl);
        R = max(R, vr);
    }else{
        if(t[v] == 1){
            dfs2(l[v], vl + sz[r[v]].x00, vr + sz[r[v]].x01);
            dfs2(r[v], vl + sz[l[v]].x00, vr + sz[l[v]].x01);
        }else{
            dfs2(l[v], vl + sz[r[v]].x10, vr + sz[r[v]].x11);
            dfs2(r[v], vl + sz[l[v]].x10, vr + sz[l[v]].x11);
        }
    }
}

int parse_string(string s){
    int id = 0;
    vector<int> v;
    vector<int> op;
    for(int i = 0; i < s.size();){
        if(s[i] == 'm'){
            string t = s.substr(i, 3);
            if(t == "max"){
                op.push_back(1);
                i += 4;
            }else if(t == "min"){
                op.push_back(2);
                i += 4;
            }else{
                assert(0 == 1);
            }
        }else if(s[i] == ')'){
            ++id;
            t[id] = op.back(); l[id] = v[v.size() - 2]; r[id] = v[v.size() - 1];
            op.pop_back(); v.pop_back(); v.pop_back(); v.push_back(id);
            i++;
        }else if(s[i] == ','){
            i++;
        }else if(s[i] == '?'){
            v.push_back(++id);
            i++;
        }
    }
    return id;
}

int32_t main(){
    string s; cin >> s;
    int root = parse_string(s); dfs(root); dfs2(root);
    int ans = R - L + 1;
    cout << ans << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int parse_string(std::string)':
Main.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = 0; i < s.size();){
      |                    ~~^~~~~~~~~~

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