oj.uz

Submission #831759

# Submission time Handle Problem Language Result Execution time Memory
831759 2023-08-20T13:36:09 Z QwertyPi Homework (CEOI22_homework) C++14
13 / 100
 214 ms 101304 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 98832 KB Output is correct
2 Correct 172 ms 98236 KB Output is correct
3 Correct 186 ms 98656 KB Output is correct
4 Correct 214 ms 99620 KB Output is correct
5 Correct 191 ms 99688 KB Output is correct
6 Correct 184 ms 98344 KB Output is correct
7 Correct 181 ms 101304 KB Output is correct
8 Correct 175 ms 99032 KB Output is correct
9 Correct 178 ms 99784 KB Output is correct
10 Correct 178 ms 98352 KB Output is correct
11 Correct 178 ms 99696 KB Output is correct
12 Correct 180 ms 98528 KB Output is correct
13 Correct 0 ms 340 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -