记录编号	461998	评测结果	AAAAAAAAAA
题目名称	艺术	最终得分	100
用户昵称	kemoto	是否通过	通过
代码语言	C++	运行时间	0.205 s
提交时间	2017-10-21 07:08:11	内存使用	225.36 MiB

#include <stdio.h>
#include <cstring>
#include <ctime>
#define Max(x,y) ((x)>(y)?(x):(y))
typedef long long ll;
const int mod = 998244353,MAXN = 4000005;
int n,fa[MAXN],c[MAXN],a[MAXN];
bool vis[MAXN]; ll Ans[MAXN],Cooook,w[MAXN];


char buf[MAXN*30], *ptr = buf - 1;
inline int read(){
    register int x = 0, f = 1, c = *++ptr;
    while (c < 48)c == '-' && (f = -1), c = *++ptr;
    while (c > 47)x = x * 10 + c - 48, c = *++ptr;
    return x * f;
}

inline int find(int x) {
    return fa[x] == x?x:fa[x] = find(fa[x]);
}

inline void Link(int x,int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    fa[x] = y;
    w[y] += w[x];
    Cooook = Max(Cooook,w[y]);
}

signed main() {
    freopen("art.in","r",stdin);
    freopen("art.out","w",stdout);
    fread(buf, 1, sizeof(buf), stdin);
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) c[i] = read(),vis[c[i]] = 1;
    // printf("%d\n",clock());
    for (int i = 1; i <= n; i++) fa[i] = i,w[i] = a[i];
    for (int i = 1; i <= n; i++)  {
        if (vis[i]) continue;
        Cooook = Max(Cooook,(ll)a[i]);
        if (i == 1) continue;
        if (!vis[i-1]) Link(i-1,i);
    }
    
    Ans[n] = Cooook;
    for (int i = n; i > 1; i--) {
        vis[c[i]] = false; Cooook = Max(Cooook,(ll)a[c[i]]); 
        if (!vis[c[i]-1] && c[i] != 1) Link(c[i],c[i]-1);
        if (!vis[c[i]+1] && c[i] != n) Link(c[i],c[i]+1);
        if (i) Ans[i-1] = Cooook;
    }
    for (int i = 1; i <= n; i++) printf("%lld\n",Ans[i]);
    // while (true);
    return 0;
}