Submission #1186733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186733		Gray	Homework (CEOI22_homework)	C++20	100 / 100	117 ms	163892 KiB

Main

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

struct SegTree{
    struct node{
        ll mx, mn, upd, tag;
    };
    vector<node> t;
    ll sz, rsz;
    SegTree(ll N){
        sz=N*4; rsz=N; t.resize(sz);
    }
    void preprocess(ll tl, ll tr, ll v){
        if (t[v].tag){
            t[v].tag=0; t[v].mx=t[v].mn=t[v].upd;
            if (tl!=tr){
                t[v*2].upd=t[v*2+1].upd=t[v].upd;
                t[v*2].tag=t[v*2+1].tag=1;
            }
        }
    }
    node merge(node l, node r){
        return {max(l.mx, r.mx), min(l.mn, r.mn), 0, 0};
    }
    void update(ll tl, ll tr, ll v, ll l, ll r, ll x){
        preprocess(tl, tr, v);
        if (tl==l and tr==r){
            t[v].upd=x; t[v].tag=1;
            preprocess(tl, tr, v);
        }else if (l>r) return;
        else{
            ll tm = (tl+tr)/2;
            update(tl, tm, v*(2), l, min(r, tm), x);
            update(tm+1, tr, v*2+1, max(l, tm+1), r, x);
            t[v] = merge(t[v*2], t[v*2+1]);
        }
    }
    void update(ll l, ll r, ll x){
        // cout << l << " - " << r << " <- " << x << ln;
        update(0, rsz-1, 1, l, r, x);
    }
    ll query(ll tl, ll tr, ll v, ll l, ll r, ll x){
        preprocess(tl, tr, v);
        if (l<=tl and tr<=r and t[v].mx<x){
            return tr-tl+1;
        }else if (l>tr or r<tl or (t[v].mn>=x)){
            return 0;
        }else{
            ll tm = (tl+tr)/2;
            return query(tl, tm, v*2, l, r, x)+query(tm+1, tr, v*2+1, l, r, x);
        }
    }
    ll query(ll l, ll r, ll x){
        // cout << l << " - " << r << " -> " << x << " = ";
        // cout << query(0, rsz-1, 1, l, r, x) << ln;
        return query(0, rsz-1, 1, l, r, x);
    }
};

array<ll, 4> eval(string &s, ll l){
    if (s[l]=='?'){
        return {0, 0, l+1, 1};
    }else{
        ll il=l; l+=4;
        array<ll, 4> ret1 = eval(s, l); l=ret1[2]+1;
        array<ll, 4> ret2 = eval(s, l); l=ret2[2]+1;
        if (s[il+1]=='a'){
            return {ret1[0]+ret2[0]+1, min(ret1[1], ret2[1]), l, ret1[3]+ret2[3]};
        }else{
            return {min(ret1[0], ret2[0]), ret1[1]+ret2[1]+1, l, ret1[3]+ret2[3]};
        }
    }
}

void solve(){
    string s; cin >> s;
    array<ll, 4> res=eval(s, 0);
    cout << res[3]-(res[1]+res[0]) << ln;
}
/*



*/
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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