Submission #23147

#	Time	Username	Problem	Language	Result	Execution time	Memory
23147		ainta	New Ocurrences (KRIII5_NO)	C++14	7 / 7	436 ms	8024 KiB

NO

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
char p[101000];
int n, C[101000], ord1[101000], ord2[101000], SA[101000], LCP[101000], Rank[101000];
struct AA{
    int a, b;
}w[101000];
void Make_SA(){
    int i, M = max(200,n), L = 1;
    for(i=0;i<n;i++)w[i].a = p[i], w[i].b = p[i+1];
    while(1){
        for(i=0;i<=M;i++)C[i]=0;
        for(i=0;i<n;i++)C[w[i].b]++;
        for(i=1;i<=M;i++)C[i]+=C[i-1];
        for(i=0;i<n;i++)ord1[--C[w[i].b]] = i;
        for(i=0;i<=M;i++)C[i]=0;
        for(i=0;i<n;i++)C[w[i].a]++;
        for(i=1;i<=M;i++)C[i]+=C[i-1];
        for(i=n-1;i>=0;i--)ord2[--C[w[ord1[i]].a]] = ord1[i];
        int cnt = 0;
        for(i=0;i<n;i++){
            if(i==0||w[ord2[i]].a!=w[ord2[i-1]].a||w[ord2[i]].b!=w[ord2[i-1]].b)cnt++;
            Rank[ord2[i]] = cnt;
        }
        if(cnt == n)break;
        L<<=1;
        for(i=0;i<n;i++){
            w[i].a=Rank[i];
            if(i+L>=n)w[i].b=0;
            else w[i].b=Rank[i+L];
        }
    }
    for(i=0;i<n;i++)SA[Rank[i]] = i;
    int t = 0, x, y;
    for(i=0;i<n;i++){
        if(t)t--;
        x = Rank[i];
        if(x==n)continue;
        y = SA[x+1];
        while(p[i+t]==p[y+t])t++;
        LCP[x] = t;
    }
}
int P[101000];
struct point{
    int x, num;
    bool operator<(const point &p)const{
        return x<p.x;
    }
};
long long BIT[101000], Res[101000];
void Add(int a, int b){
    a++;
    while(a<=n){
        BIT[a] += b;
        a+=(a&-a);
    }
}
long long Sum(int a){
    a++;
    long long r = 0;
    while(a){
        r+=BIT[a];
        a-=(a&-a);
    }
    return r;
}
void Pro(vector<point> &A, vector<point>&B){
    int i, pv = 0, sz = B.size(), c = 0;
    long long s = 0;
    for(i=0;i<A.size();i++){
        while(pv != sz && B[pv].x <= A[i].x){
            Add(B[pv].num, B[pv].x);
            s += B[pv].x;
            pv++;
        }
        Res[A[i].num] += s - Sum(A[i].num);
    }
    for(i=0;i<pv;i++)Add(B[i].num,-B[i].x);
    pv = sz-1;
    for(i=A.size()-1;i>=0;i--){
        while(pv >= 0 && B[pv].x > A[i].x){
            Add(B[pv].num, 1);
            c++;
            pv--;
        }
        Res[A[i].num] += (c - Sum(A[i].num))*A[i].x;
    }
    for(i=pv+1;i<sz;i++)Add(B[i].num,-1);
}
void Do(int b, int e){
    if(b==e)return;
    int i;
    int m = (b+e)>>1;
    Do(b,m);
    Do(m+1,e);
    int t = n;
    for(i=m+1;i<=e;i++){
        t = min(t, LCP[i-1]);
        P[i] = t;
    }
    t = n;
    for(i=m;i>=b;i--){
        t = min(t, LCP[i]);
        P[i] = t;
    }
    vector<point>A, B;
    for(i=b;i<=m;i++)A.push_back({P[i],SA[i]});
    for(i=m+1;i<=e;i++)B.push_back({P[i],SA[i]});
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    Pro(A,B);
    Pro(B,A);
}
int main(){
    int i;
    scanf("%s",p);
    for(i=0;p[i];i++);
    n = i;
    for(i=0;i<n/2;i++)swap(p[i],p[n-i-1]);
    Make_SA();
    Do(1,n);
    long long s = 0;
    for(i=1;i<=n;i++){
        s += Res[n-i]*2+i;
        printf("%lld\n",s);
    }
}

Compilation message (stderr)

NO.cpp: In function 'void Pro(std::vector<point>&, std::vector<point>&)':
NO.cpp:73:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<A.size();i++){
              ^
NO.cpp: In function 'int main()':
NO.cpp:119:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",p);
                  ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5