Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- const int N=6e5+7;
- const int INF=1e9;
- int tot;
- int len[N],fa[N],trans[N][26],siz[N];
- int mx[N],_mx[N],mi[N],_mi[N];
- vector<int>G[N];
- inline int NewNode(int l,int *tr,int su){
- ++tot;
- fa[tot]=su;
- len[tot]=l;
- mi[tot]=_mi[tot]=INF;
- mx[tot]=_mx[tot]=-INF;
- if(tr!=NULL)memcpy(trans[tot],tr,26<<2);
- return tot;
- }
- inline int Extend(int u,int c){
- int t=NewNode(len[u]+1,NULL,0);
- for(;u&&!trans[u][c];u=fa[u])trans[u][c]=t;
- if(!u){
- fa[t]=1;
- return t;
- }
- int v=trans[u][c];
- if(len[v]==len[u]+1){
- fa[t]=v;
- return t;
- }
- int x=NewNode(len[u]+1,trans[v],fa[v]);
- fa[t]=fa[v]=x;
- for(;u&&trans[u][c]==v;u=fa[u])trans[u][c]=x;
- return t;
- }
- inline void Max(int x,int v){
- if(v>=mx[x])_mx[x]=mx[x],mx[x]=v;
- else if(v>_mx[x])_mx[x]=v;
- }
- inline void Min(int x,int v){
- if(v<=mi[x])_mi[x]=mi[x],mi[x]=v;
- else if(v<_mi[x])_mi[x]=v;
- }
- ll sum[N],ans[N];
- void dfs(int x){
- for(int i=0;i<G[x].size();++i){
- int v=G[x][i];
- dfs(v);
- sum[len[x]]+=(ll)siz[x]*siz[v];
- siz[x]+=siz[v];
- Max(x,mx[v]);
- Max(x,_mx[v]);
- Min(x,mi[v]);
- Min(x,_mi[v]);
- }
- if(siz[x]>1)ans[len[x]]=max(ans[len[x]],max((ll)mx[x]*_mx[x],(ll)mi[x]*_mi[x]));
- }
- int w[N];
- char s[N];
- int main(){
- int n;r(n);
- scanf("%s",s);
- for(int i=0;i<n;++i)r(w[i]);
- int lst=NewNode(0,NULL,0);
- for(int i=n-1;~i;--i){
- lst=Extend(lst,s[i]-'a');
- mx[lst]=mi[lst]=w[i];
- siz[lst]=1;
- ans[i]=-1e18;
- }
- for(int i=2;i<=tot;++i)G[fa[i]].push_back(i);
- dfs(1);
- for(int i=n-2;~i;--i){
- sum[i]+=sum[i+1];
- ans[i]=max(ans[i],ans[i+1]);
- }
- for(int i=0;i<n;++i){
- printf("%lld %lld\n",sum[i],sum[i]?ans[i]:0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement