제출 #769252

#제출 시각아이디문제언어결과실행 시간메모리
769252danikoynovCat Exercise (JOI23_ho_t4)C++14
74 / 100
2072 ms59956 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 2e5 + 10; int n, a[maxn], used[maxn], pos[maxn]; vector < int > adj[maxn]; ll dp[maxn]; int rec(int val) { if (used[val]) return dp[val]; used[val] = 1; int left = 0, right = n + 1; for (int i = n; i > val; i --) { if (pos[i] > pos[val]) { right = min(right, pos[i]); } else { left = max(left, pos[i]); } } int mx = -1; for (int i = pos[val] + 1; i < right; i ++) { if (a[i] > mx) { mx = a[i]; dp[val] = max(dp[val], (ll)(i - pos[val] + rec(a[i]))); } } mx = -1; for (int i = pos[val] - 1; i > left; i --) { if (a[i] > mx) { mx = a[i]; dp[val] = max(dp[val], (ll)(pos[val] - i + rec(a[i]))); } } return dp[val]; } int dfs(int v, int p, int mx, int dis, int val) { if (mx > val) return 0; int ans = 0; if (a[v] == mx) ans = max((ll)ans, dis + dp[v]); for (int u : adj[v]) { if (u == p) continue; ans = max(ans, dfs(u, v, max(mx, a[u]), dis + 1, val)); } return ans; } int bef[maxn], aft[maxn]; pair < int, int > tree[4 * maxn]; void build_tree(int root, int left, int right) { if (left == right) { tree[root] = {a[left], left}; return; } int mid = (left + right) / 2; build_tree(root * 2, left, mid); build_tree(root * 2 + 1, mid + 1, right); tree[root] = max(tree[root * 2], tree[root * 2 + 1]); } pair < int, int > query(int root, int left, int right, int qleft, int qright) { if (left > qright || right < qleft) return {-1, -1}; if (left >= qleft && right <= qright) return tree[root]; int mid = (left + right) / 2; return max(query(root * 2, left, mid, qleft, qright), query(root * 2 + 1, mid + 1, right, qleft, qright)); } int best[maxn], par[maxn], depth[maxn]; int tin[maxn], tout[maxn], timer; int occ[2 * maxn]; void trav(int v) { occ[++ timer] = v; tin[v] = timer; for (int u : adj[v]) { if (u == par[v]) continue; depth[u] = depth[v] + 1; par[u] = v; trav(u); occ[++ timer] = v; } tout[v] = timer; } const int maxlog = 20; int fp[maxlog][2 * maxn], lg[2 * maxn]; void build_sparse_table() { for (int i = 1; i <= timer; i ++) { lg[i] = lg[i / 2] + 1; fp[0][i] = occ[i]; } for (int j = 1; j < lg[timer]; j ++) for (int i = 1; i <= timer - (1 << j) + 1; i ++) { fp[j][i] = fp[j - 1][i + (1 << (j - 1))]; if (depth[fp[j - 1][i]] < depth[fp[j][i]]) fp[j][i] = fp[j - 1][i]; } } int lca_query(int v, int u) { int l = tin[v], r = tin[u]; if (l > r) swap(l, r); int len = lg[r - l + 1] - 1, lca = fp[len][r - (1 << len) + 1]; if (depth[fp[len][l]] < depth[lca]) lca = fp[len][l]; return lca; } int distance(int v, int u) { return depth[v] + depth[u] - 2 * depth[lca_query(v, u)]; } void solve() { cin >> n; for (int i = 1; i <= n; i ++) { cin >> a[i]; pos[a[i]] = i; } bool chain = true; for (int i = 1; i < n; i ++) { int v, u; cin >> v >> u; if (!(v == i && u == i + 1)) chain = false; adj[v].push_back(u); adj[u].push_back(v); } if (chain) { stack < int > st; for (int i = 1; i <= n; i ++) { while(!st.empty() && a[st.top()] < a[i]) st.pop(); if (!st.empty()) bef[i] = st.top(); ///cout << "stack " << i << " " << st.top() << endl; st.push(i); } while(!st.empty()) st.pop(); for (int i = n; i > 0; i --) { while(!st.empty() && a[st.top()] < a[i]) st.pop(); if (!st.empty()) aft[i] = st.top(); else aft[i] = n + 1; st.push(i); } build_tree(1, 1, n); for (int i = 1; i <= n; i ++) { int v = pos[i]; ///cout << "now " << v << " " << bef[v] << " " <<aft[v] << endl; pair < int, int > lf = query(1, 1, n, bef[v] + 1, v - 1); pair < int, int > rf = query(1, 1, n, v + 1, aft[v] - 1); ///cout << v << " " << lf.second << " " << rf.second << endl; if (lf.first != -1) { ///cout << "here " << dp[lf.first] << " " << lf.first << endl; dp[v] = max(dp[v], dp[lf.second] + (ll)(v - lf.second)); } if (rf.first != -1) dp[v] = max(dp[v], dp[rf.second] + (ll)(rf.second - v)); //cout << dp[v] << endl; } cout << dp[pos[n]] << endl; } else { trav(1); build_sparse_table(); for (int i = 1; i <= n; i ++) { int v = pos[i]; //cout << "step" << endl; //cout << v << endl; for (int u : adj[v]) { ///cout << u << endl; if (u == par[v]) continue; ///cout << "fine" << endl; if (best[u] != 0) { ///cout << "here " << best[u] << endl; dp[v] = max(dp[v], dp[pos[best[u]]] + distance(v, pos[best[u]])); } } int ver = par[v]; while(ver != 0) { if (a[ver] > i) break; //cout << "check " << v << " " << ver << " " << best[ver] << " " << pos[best[ver]] << " " << dp[best[ver]] << endl; dp[v] = max(dp[v], dp[pos[best[ver]]] + distance(v, pos[best[ver]])); ver = par[ver]; } ver = v; while(ver != 0) { if (a[ver] > i) break; best[ver] = i; ver = par[ver]; } ///cout << "dp " << v << " " << dp[v] << endl; } cout << dp[pos[n]] << endl; } } int main() { solve(); return 0; } /** 5 5 3 2 1 4 1 2 2 3 3 4 4 5 */
#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...