제출 #831759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831759		QwertyPi	Homework (CEOI22_homework)	C++14	13 / 100	214 ms	101304 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;
        }
    }
}

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);
    int ans;
    if(t[root] == 1){
        ans = sz[root].x01 - sz[root].x00 + 1;
    }else{
        ans = sz[root].x11 - sz[root].x10 + 1;
    }
    cout << ans << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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