Submission #956815

#TimeUsernameProblemLanguageResultExecution timeMemory
956815LukapHomework (CEOI22_homework)C++14
100 / 100
151 ms184724 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e6; string s; int n, uk; int l[MAXN], r[MAXN], tip[MAXN], lo[MAXN], hi[MAXN], vel[MAXN]; vector<int> v; vector<int> zarez[MAXN]; int koji[MAXN]; void unos (int l_g, int r_g, int xi) { int x = uk; uk++; if (r_g == l_g) { n++; return; } char a = s[l_g + 1]; int zag = zarez[xi][koji[xi]]; koji[xi]++; if (a == 'i') tip[x] = 0; else tip[x] = 1; l[x] = uk; unos (l_g + 4, zag - 1, xi + 1); r[x] = uk; unos (zag + 1, r_g - 1, xi + 1); } void dfs (int x) { if (l[x] == -1) { vel[x] = 1; lo[x] = 1; hi[x] = 1; return; } dfs (l[x]); dfs (r[x]); vel[x] = vel[l[x]] + vel[r[x]]; if (!tip[x]) { lo[x] = min (lo[l[x]], lo[r[x]]); hi[x] = hi[l[x]] + hi[r[x]] - 1; } else { lo[x] = lo[l[x]] + lo[r[x]]; hi[x] = max (hi[l[x]] + vel[r[x]], hi[r[x]] + vel[l[x]]); } } int main () { ios_base::sync_with_stdio(false); cin.tie (0); cout.tie (0); memset (l , -1, sizeof (l)); memset (r, -1, sizeof (r)); cin >> s; int brojem = 0; for (int i = 0; i < (int) s.size (); i++) { if (s[i] == '(') brojem++; if (s[i] == ')') brojem--; if (s[i] == ',') zarez[brojem - 1].push_back (i); } unos (0, s.size () - 1, 0); dfs (0); cout << hi[0] - lo[0] + 1; return 0; }
#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...