Submission #1167387

#TimeUsernameProblemLanguageResultExecution timeMemory
1167387SyriusCat Exercise (JOI23_ho_t4)C++20
41 / 100
166 ms45664 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define ff first #define ss second #define pint pair < int , int > #define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL) typedef vector < int > vint; const int inf = 1e18 + 9; const int mxn = 2e5 + 2; const int mod = 1e9 + 7; int a[mxn]; struct node { int tl , tm , tr; int id; node *left , *right; node (int l , int r) { tl = l , tr = r , tm = (l + r) / 2; if (tl == tr) { id = tl; return; } left = new node(tl , tm); right = new node(tm+1 , tr); id = (a[left->id] > a[right->id]) ? left->id : right->id; } int query(int l , int r) { if (tl == l && tr == r) return id; if (r <= tm) return left -> query(l , r); else if (l > tm) return right -> query(l , r); int idl = left -> query(l , tm); int idr = right -> query(tm+1 , r); return (a[idl] > a[idr]) ? idl : idr; } } *root; int dfs(int l , int r) { if (l == r) return 0; int x = root -> query(l , r); int t1 = -inf , t2 = -inf; if (x != r) t1 = root -> query(x+1 , r) - x + dfs(x+1 , r); if (x != l) t2 = x - root -> query(l , x-1) + dfs(l , x-1); return max(t1 , t2); } signed main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 0; i < n-1; i++) { int x , y; cin >> x >> y; } root = new node(1 , n); cout << dfs(1 , n) << '\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...