Submission #1030676

#TimeUsernameProblemLanguageResultExecution timeMemory
1030676mispertionHomework (CEOI22_homework)C++17
100 / 100
156 ms167136 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; #define int ll typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define F first #define S second #define getlast(s) (*s.rbegin()) #define debg cout << "OK\n" const ld PI = 3.1415926535; const int N = 3e6+10; const int M = 1e4 + 5; int mod = 1e9+7; const int infi = INT_MAX; const ll infl = LLONG_MAX; const int P = 467743; int mult(int a, int b) { return a * 1LL * b % mod; } int sum(int a, int b) { a %= mod; b %= mod; if(a + b >= mod) return a + b - mod; if(a + b < 0) return a + b + mod; return a + b; } int binpow(int a, ll n) { if (n == 0) return 1; if (n % 2 == 1) { return mult(binpow(a, n - 1), a); } else { int b = binpow(a, n / 2); return mult(b, b); } } int n, tp[N], cr, l[N], r[N]; string expr; vector<int> g[N]; void solve(){ cin >> expr; int mx = sz(expr); expr += "$$"; int i = 0; stack<int> st; while(i < mx){ if(expr[i] == 'm'){ cr++; if(sz(st) > 0) g[st.top()].pb(cr); st.push(cr); if(expr[i + 1] == 'i') tp[cr] = -1; else tp[cr] = 1; i += 4; }else if(expr[i] == '?'){ n++; cr++; if(sz(st) > 0) g[st.top()].pb(cr); while(expr[i + 1] == ')'){ st.pop(); i++; } i += 2; } } for(int v = cr; v >= 1; v--){ if(tp[v] == 0){ l[v] = 0; r[v] = 0; }else if(tp[v] == 1){ r[v] = min(r[g[v][0]], r[g[v][1]]); l[v] = l[g[v][0]] + l[g[v][1]] + 1; }else{ l[v] = min(l[g[v][0]], l[g[v][1]]); r[v] = r[g[v][0]] + r[g[v][1]] + 1; } } cout << n - l[1] - r[1] << '\n'; } signed main() { mispertion; int t = 1; //cin >> t; while(t--){ solve(); } return 0; } // coded by mispertion :)
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...