Submission #990862

#	Time	Username	Problem	Language	Result	Execution time	Memory
990862		alexdumitru	Homework (CEOI22_homework)	C++14	100 / 100	121 ms	163028 KiB

Main

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

string s;
vector<int> virgula;

struct Node {
    int l, r, sz;
};

Node combine(Node a, Node b, bool isMIN) {
    Node ans;
    ans.sz = a.sz + b.sz;
    if (isMIN) {
        ans.l = min(a.l, b.l);
        ans.r = a.r + b.r - 1;
    } else {
        ans.l = a.l + b.l;
        ans.r = max(a.r + b.sz, b.r + a.sz);
    }
    return ans;
}

Node go(int st, int dr) {
    if (st == dr) {
        //?
        return {1, 1, 1};
    }

    bool operatie = false;

    if (s[st + 1] == 'i')
        operatie = true;

    int pos = virgula[st + 3];

    return combine(go(st + 4, pos - 1), go(pos + 1, dr - 1), operatie);
}

void solve() {
    cin >> s;
    virgula.resize(s.length());
    stack<int> stk;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            stk.push(i);
        } else if (s[i] == ',') {
            virgula[stk.top()] = i;
            stk.pop();
        }
    }
    Node ans = go(0, s.length() - 1);
    cout << ans.r - ans.l + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message (stderr)

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

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