Submission #666177

#	Time	Username	Problem	Language	Result	Execution time	Memory
666177		ParsaS	Homework (CEOI22_homework)	C++17	100 / 100	352 ms	167600 KiB

Main

// In the name of God
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5;
string s;
bool f[N];
map<ll, int> M;

inline ll F(int l, int r) {
    return l + 1LL * r * N;
}

pair<int, int> SOLVE(int L, int R) {
    pair<int, int> ans;
    //cout << L << ' ' << R << ' ' << v << endl;
    if (L >= R)
        return mp(1, 1);
    int v = M[F(L, R)];
    if (L == R - 1) {
        return f[v] ? mp(2, 2) : mp(1, 1);
    }
    int mid = v;
    pair<int, int> lt = SOLVE(L, mid - 1);
    pair<int, int> rt = SOLVE(mid, R);
    int n = R - L + 1, cl = mid - L, cr = R - mid + 1;
    if (f[v]) {
        ans.fi = lt.fi + rt.fi;
        ans.se = n - min(cl - lt.se, cr - rt.se);
    }
    else {
        ans.fi = min(lt.fi, rt.fi);
        ans.se = lt.se + rt.se - 1;
    }
    return ans;
}

void solve() {
    cin >> s;
    vector<pair<pair<int, int>, bool> > st;
    int cnt = 1;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
           st.pb(mp(mp(cnt - 1, 0), s[i - 1] == 'x'));
        }
        else if (s[i] == ',') {
            st.back().fi.se = cnt++;
        }
        else if (s[i] == ')') {
            pair<pair<int, int>, bool> p = st.back();
            st.pop_back();

            M[F(p.fi.fi, cnt - 1)] = p.fi.se;
            f[p.fi.se] = p.se;
        } 
    }
    pair<int, int> p = SOLVE(0, cnt - 1);
    cout << p.se - p.fi + 1 << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    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.size(); i++) {
      |                     ~~^~~~~~~~~~

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