| 1 |
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 2e18 + 1; int mx = 0; vector<int> a, b; struct DSU { vector<int> pr; vector<int> sz; vector<int> sm; DSU (int n) { pr.resize(n + 1, 0); sz.resize(n + 1, 1); sm.resize(n + 1, 0); for (int i = 0; i <= n; ++i) pr[i] = i; for (int i = 0; i < n; ++i) sm[i + 1] = a[i]; } int froot(int x) { if (pr[x] == x) return x; return pr[x] = froot(pr[x]); } void unite(int x, int y) { int rx = froot(x); int ry = froot(y); if (rx == ry) return; if (sz[ry] > sz[rx]) swap(rx, ry); sz[rx] += sz[ry]; pr[ry] = rx; sm[rx] += sm[ry]; mx = max(mx, sm[rx]); } }; signed main() { int n; cin >> n; a.resize(n); b.resize(n); for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; reverse(b.begin(), b.end()); vector<int> used(n + 1, 0); DSU dsu(n); vector<int> ans; for (int i = 0; i < n; ++i) { ans.push_back(mx); used[b[i]] = 1; if (b[i] > 1 && used[b[i] - 1]) { dsu.unite(b[i] - 1, b[i]); } if (b[i] < n && used[b[i] + 1]) { dsu.unite(b[i], b[i] + 1); } mx = max(mx, a[b[i] - 1]); } reverse(ans.begin(), ans.end()); for (int el : ans) cout << el << '
'; } |
Комментарии