Submission #953698

#TimeUsernameProblemLanguageResultExecution timeMemory
953698GrindMachineHomework (CEOI22_homework)C++17
100 / 100
213 ms190232 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* refs: https://youtu.be/N69P-6MZor0?list=PLg_Krngrs0eC_1vn0dTjyPZMkwBOcVsgH edi */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; struct node{ ll typ; node *l, *r; node(){ typ = -1; l = r = nullptr; } node(ll t){ typ = t; l = r = nullptr; } void insert(node* u){ if(!l) l = u; else{ if(r != nullptr){ debug(u->typ); } r = u; } } }; array<ll,3> dfs(node *u){ assert(u); if(u->typ == 3){ return {1,1,1}; } auto [l1,r1,s1] = dfs(u->l); auto [l2,r2,s2] = dfs(u->r); ll l3 = -1, r3 = -1; ll s3 = s1+s2; if(u->typ == 1){ l3 = l1+l2; r3 = max(s1+r2,s2+r1); } else{ l3 = min(l1,l2); r3 = r1+r2-1; } return {l3,r3,s3}; } void solve(int test_case) { string s; cin >> s; ll n = sz(s); string new_s = ""; rep(i,sz(s)){ if(isalpha(s[i])) conts; if(s[i] == '('){ if(s[i-1] == 'n'){ new_s.pb('('); } else{ new_s.pb('['); } } else{ new_s.pb(s[i]); } } s = new_s; n = sz(s); stack<node*> stk; rep(i,n){ auto ch = s[i]; if(ch == '['){ stk.push(new node(1)); } if(ch == '('){ stk.push(new node(2)); } if(ch == '?'){ stk.push(new node(3)); } if(ch == ',' or ch == ')'){ auto curr = stk.top(); stk.pop(); stk.top()->insert(curr); } } auto root = stk.top(); auto [l,r,siz] = dfs(root); ll ans = r-l+1; cout << ans << endl; } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }

Compilation message (stderr)

Main.cpp: In member function 'void node::insert(node*)':
Main.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define debug(x) 42
      |                  ^~
Main.cpp:80:17: note: in expansion of macro 'debug'
   80 |                 debug(u->typ);
      |                 ^~~~~
#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...