oj.uz

Submission #109865

# Submission time Handle Problem Language Result Execution time Memory
109865 2019-05-08T08:12:30 Z sealnot123 Palindromes (APIO14_palindrome) C++14
65 / 100
 1000 ms 88220 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define ep emplace_back
#define sz(a) (a).size()
#define R real()
#define I imag()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
typedef complex<LL> cd;
const int N=300007,lgn=20;
char str[2*N];
int suffix[2*N],lcp[2*N],Rank[2*N],tRank[2*N],stRank[2*N],tsuffix[2*N],fsuffix[2*N],nxt[2*N];
int LCA[lgn][2*N],now,mk[2*N],level[2*N],top;
PII line[2*N];
struct A{
    LL a,b,c;
};
A sta[2*N];
PII intersect(PII a, PII b){
    PII tmp = {a.y-b.y, b.x-a.x};
    if(tmp.y<0) tmp.x*=-1,tmp.y*=-1;
    return tmp;
}
void print(int idx){
    while(idx) printf("====%lld %lld\n",line[idx].x,line[idx].y),idx=LCA[0][idx];
}
int push(int idx, LL m, LL c){
    line[++now] = {m,c};
    LCA[0][now]=idx;
    level[now]=level[idx]+1;
    int i;
    for(i=1;i<=19;i++) LCA[i][now] = LCA[i-1][LCA[i-1][now]];
    int tmp=now;
    for(i=19;i>=0;i--){
        if(level[LCA[i][tmp]]>1){
            int p=LCA[i][tmp];
            int q=LCA[0][p];
            PII line1 = intersect(line[p],line[q]), line2 = intersect(line[p],line[now]);
            if(line2.x*line1.y<=line1.x*line2.y) tmp = LCA[i][tmp];
        }
    }
    LCA[0][now]=LCA[0][tmp];
    for(i=1;i<=19;i++) LCA[i][now]=LCA[i-1][LCA[i-1][now]];
    level[now]=level[LCA[0][now]]+1;
    return now;
}
bool cmp(int a, int b){
    return str[a]<str[b];
}
void suffix_array(int n){
    int i,j,k,h,cnt;
    memset(Rank, -1, sizeof Rank);
    for(i=1;i<=n;i++) suffix[i]=i;
    sort(suffix+1, suffix+1+n, cmp);
    for(i=1,cnt=0;i<=n;i++){
        if(str[suffix[i]]!=str[suffix[i-1]]) cnt++;
        Rank[suffix[i]]=cnt;
    }
    for(h=1;h<n;h<<=1){
        for(i=1;i<=n;i=j){
            for(j=i;j<=n&&Rank[suffix[i]]==Rank[suffix[j]];j++) stRank[suffix[j]]=i;
            nxt[i]=j; fsuffix[i]=i;
        }
        for(i=n;i>=n-h+1;i--){
            tsuffix[fsuffix[stRank[i]]]=i;
            fsuffix[stRank[i]]++;
        }
        for(i=1;i<=n;i=nxt[i]){
            for(j=i;j<nxt[i];j++){
                if(suffix[j]-h<=0) continue;
                int p = suffix[j]-h;
                tsuffix[fsuffix[stRank[p]]]=suffix[j]-h;
                fsuffix[stRank[p]]++;
            }
        }
        for(i=1;i<=n;i++) suffix[i]=tsuffix[i];
        for(i=1,cnt=1;i<=n;i=j){
            for(j=i;j<=n&&Rank[suffix[i]]==Rank[suffix[j]]&&Rank[suffix[i]+h]==Rank[suffix[j]+h];j++) tRank[suffix[j]]=cnt;
            cnt++;
        }
        for(i=1;i<=n;i++) Rank[i]=tRank[i];
    }
    int t=0;
    for(i=1;i<=n;i++){
        while(Rank[i]<n && i+t<=n && str[i+t]==str[suffix[Rank[i]+1]+t]) t++;
        lcp[Rank[i]] = t;
//        printf("%d %d %d\n",i,Rank[i],t);
        if(t) t--;
    }
}
LL calc(int idx, LL V){
    int i;
    if(level[idx]==1) return line[idx].x*V+line[idx].y;
    PII tmp = intersect(line[idx], line[LCA[0][idx]]);
    if(V*tmp.y>=tmp.x) return line[idx].x*V+line[idx].y;
    // binary search!
    for(i=18;i>=0;i--){
        if(level[idx]>1){
            int p = LCA[i][idx];
            int q = LCA[0][p];
            tmp = intersect(line[p],line[q]);
            if(V*tmp.y<tmp.x) idx = LCA[i][idx];
        }
    }
    idx = LCA[0][idx];
    return line[idx].x*V+line[idx].y;
}
int main(){
    int n,i,j,k,len;
    scanf("%s",str+1);
    len = strlen(str+1);
    str[len+1]='#';
    for(i=1;i<=len;i++){
        str[2*len+2-i]=str[i];
    }
    str[2*len+2]='&';
    len+=len+2;
    suffix_array(len);
    for(i=1;i<=len;i++){
        if(suffix[i]>len/2) mk[i]=2;
        else mk[i]=1;
    }
//    for(i=1;i<=len;i++) printf("%d : %d %d %s\n",i,lcp[i],mk[i],str+suffix[i]);
    LL ans=0;
    sta[top++]={-1<<30,0,0};
    int last1=0,last2=0;
    for(i=1;i<=len;i++){
        int fin;
//        printf("print stack #%d:\n",i);
//        for(j=1;j<top;j++) printf("%lld %lld %lld\n",sta[j].a,sta[j].b,sta[j].c);
//        print(sta[top-1].c);
        if(mk[i]==1) last1=i,fin=last2;
        else last2=i,fin=last1;
        int l=0,r=top-1,m;
        if(fin){
            while(l<r){
                m = (l+r)>>1;
                if(sta[m].b<fin) l=m+1;
                else r=m;
            }
//            printf("***%d %d %d %lld\n",i,sta[l].b,l,calc(sta[l].c,i));
            ans = max(ans, calc(sta[l].c,i));
        }
        while(top && sta[top-1].a>=lcp[i]) top--;
        sta[top]={lcp[i],i,push(sta[top-1].c, lcp[i], -(LL)lcp[i]*sta[top-1].b)},top++;
    }
    assert((ans&1)==0);
    printf("%lld",ans/2);
    return 0;
}

Compilation message

palindrome.cpp: In function 'void suffix_array(int)':
palindrome.cpp:54:13: warning: unused variable 'k' [-Wunused-variable]
     int i,j,k,h,cnt;
             ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:112:9: warning: unused variable 'n' [-Wunused-variable]
     int n,i,j,k,len;
         ^
palindrome.cpp:112:13: warning: unused variable 'j' [-Wunused-variable]
     int n,i,j,k,len;
             ^
palindrome.cpp:112:15: warning: unused variable 'k' [-Wunused-variable]
     int n,i,j,k,len;
               ^
palindrome.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",str+1);
     ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2944 KB Output is correct
2 Correct 5 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Correct 4 ms 2944 KB Output is correct
5 Correct 4 ms 2944 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 5 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 4 ms 2944 KB Output is correct
11 Correct 5 ms 2844 KB Output is correct
12 Correct 4 ms 2816 KB Output is correct
13 Correct 4 ms 2944 KB Output is correct
14 Correct 4 ms 2944 KB Output is correct
15 Correct 5 ms 2944 KB Output is correct
16 Correct 4 ms 2944 KB Output is correct
17 Correct 5 ms 2944 KB Output is correct
18 Correct 4 ms 2944 KB Output is correct
19 Correct 4 ms 2944 KB Output is correct
20 Correct 5 ms 2944 KB Output is correct
21 Correct 6 ms 2944 KB Output is correct
22 Correct 5 ms 2944 KB Output is correct
23 Correct 4 ms 2944 KB Output is correct
24 Correct 5 ms 2936 KB Output is correct
25 Correct 5 ms 2944 KB Output is correct
26 Correct 5 ms 2944 KB Output is correct
27 Correct 5 ms 2944 KB Output is correct
28 Correct 5 ms 2944 KB Output is correct
29 Correct 5 ms 2944 KB Output is correct
30 Correct 5 ms 2944 KB Output is correct
31 Correct 5 ms 2944 KB Output is correct
32 Incorrect 6 ms 2944 KB Output isn't correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3200 KB Output is correct
2 Correct 5 ms 3200 KB Output is correct
3 Correct 6 ms 3200 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 5 ms 3232 KB Output is correct
6 Correct 6 ms 3200 KB Output is correct
7 Correct 7 ms 3200 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 5 ms 3200 KB Output is correct
10 Correct 6 ms 3200 KB Output is correct
11 Correct 5 ms 3200 KB Output is correct
12 Correct 6 ms 3200 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5752 KB Output is correct
2 Correct 16 ms 5632 KB Output is correct
3 Correct 20 ms 5752 KB Output is correct
4 Correct 21 ms 5760 KB Output is correct
5 Correct 21 ms 5504 KB Output is correct
6 Correct 20 ms 5632 KB Output is correct
7 Correct 15 ms 5632 KB Output is correct
8 Correct 22 ms 5504 KB Output is correct
9 Correct 19 ms 5508 KB Output is correct
10 Correct 17 ms 5504 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 31276 KB Output is correct
2 Correct 203 ms 30328 KB Output is correct
3 Correct 258 ms 31608 KB Output is correct
4 Correct 178 ms 30460 KB Output is correct
5 Correct 219 ms 29052 KB Output is correct
6 Correct 209 ms 29048 KB Output is correct
7 Correct 167 ms 29452 KB Output is correct
8 Correct 299 ms 29128 KB Output is correct
9 Correct 338 ms 29692 KB Output is correct
10 Correct 184 ms 28920 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 84300 KB Output is correct
2 Correct 431 ms 81768 KB Output is correct
3 Correct 968 ms 88220 KB Output is correct
4 Correct 706 ms 83656 KB Output is correct
5 Execution timed out 1086 ms 81208 KB Time limit exceeded
6 Halted 0 ms 0 KB -