Submission #941870

#	Time	Username	Problem	Language	Result	Execution time	Memory
941870		Ludissey	Homework (CEOI22_homework)	C++14	100 / 100	75 ms	64808 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define sz(a) (int)a.size()
const int mod=1e9+7;
int n;

struct op {
    int l,r,sz;
    int type; //0:?  1:max  2:min
    void updt(op a, op b){
        if(type==0) {
            l=1;
            r=1;
            sz=1;
        }else if(type==1){
            sz=a.sz+b.sz;
            l=a.l+b.l;
            r=max(b.sz+a.r,a.sz+b.r);
        }else{
            sz=a.sz+b.sz;
            l=min(a.l,b.l);
            r=(a.r+b.r)-1;
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
	string s; getline(cin,s);
    stack<op> l;
    for (int i = 0; i < sz(s); i++)
    {
        if(s[i]=='m'){
            if(s[i+1]=='a') l.push(op{0,0,0,1});
            else l.push(op{0,0,0,2});
            i+=3;
        }
        else if(s[i]=='?') {
            l.push(op{1,1,1,0});
        }
        else if(s[i]==')'){
            op a=l.top(); l.pop();
            op b=l.top(); l.pop();
            l.top().updt(a,b);
        }
    }
    cout << (l.top().r-l.top().l+1);
    return 0;
}

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