Submission #1167376

#TimeUsernameProblemLanguageResultExecution timeMemory
1167376akacool445kCat Exercise (JOI23_ho_t4)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back #define int long long #define pint pair<int, int> #define vint vector<int> const int mod = 1e9 + 7; const int mxn = 2e5 + 5; const int say = INT_MAX / 2; const int gex = INT_MIN / 2; const long long oo = 1e18; int p[mxn], pos[4 * mxn]; int n; int build(int id, int L, int R) { if(L == R) { pos[id] = L; return L; } int M = (L + R) / 2, x = 2 * id + 1, y = x + 1; int aa = build(x, L, M); int bb = build(y, M + 1, R); if(p[aa] > p[bb]) { pos[id] = aa; return aa; } else { pos[id] = bb; return bb; } } int query(int id, int L, int R, int l, int r) { if(L == l && r == R) { return pos[id]; } int M = (L + R) / 2, x = 2 * id + 1, y = x + 1; if(r <= M) return query(x, L, M, l, r); if(l > M) return query(y, M + 1, R, l, r); int aa = query(x, L, M, l, M); int bb = query(y, M + 1, R, M + 1, r); if(p[aa] > p[bb]) return aa; else return bb; } bool vis[mxn]; int dep[mxn]; void dfs(int l, int r, int par) { // cout << "hi"; if(l > r || l < 0 || r > n) return; if(l == r) { dep[l] = dep[par] + 1; return; } int id = query(0, 0, n - 1, l, r); if(par == -1) dep[id] = 1; else dep[id] = dep[par] + 1; dfs(id + 1, r, id); dfs(l, id - 1, id); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; // int p[n]; for(int i = 0; i < n; i++) cin >> p[i]; for(int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; } build(0, 0, n - 1); dfs(0, n - 1, -1); int ans = 0; for(int i = 0; i < n; i++) { ans = max(ans, dep[i]); } cout << ans << '\n'; // int q; cin >> q; // while(q--) { // int l, r; cin >> l >> r; // cout << query(0, 0, n - 1, l , r) << '\n'; // } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...